2012年10月--2007年1月自考2331数据结构历年试题和答案
数据结构试题
课程代码：02331
请考生按规定用笔将所有试题的答案涂、写在答题纸上.
选择题部分
注意事项：
1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。
2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。
一、单项选择题（本大题共l5小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 纸\"的相应代码涂黑.错涂、多涂或未涂均无分。 1．一个算法的时间耗费的数量级称为该算法的 A．效率 C．可实现性 2．顺序表便于 A．插入结点 C．按值查找结点
B．删除结点 D．按序号查找结点 B．难度 D．时间复杂度
3．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是 A．p—〉next->next==head C．p—〉next—>next==NULL
B．p-〉next==head D．p—>next==NULL
4．设以数组A[0.。m-1］存放循环队列,front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为 A．（rear-front+m)％m C．(front—rear+m）％m
B．rear—front+1 D．（rear-front）％m
1 / 100
5．下列关于顺序栈的叙述中，正确的是
A．入栈操作需要判断栈满,出栈操作需要判断栈空 B．入栈操作不需要判断栈满，出栈操作需要判断栈空 C．入栈操作需要判断栈满，出栈操作不需要判断栈空 D．入栈操作不需要判断栈满，出栈操作不需要判断栈空
6．A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a0,0的存储地址为1,每个元素占一个存储单元，则a7，5的地址为 A．25 C．33
7．树的后序遍历等价于该树对应二叉树的 A．层次遍历 C．中序遍历
8．使用二叉线索树的目的是便于 A．二叉树中结点的插入与删除 C．确定二叉树的高度
B．在二叉树中查找双亲 D．查找一个结点的前趋和后继 B．前序遍历 D．后序遍历 B．26 D．34
9．设无向图的顶点个数为n，则该图边的数目最多为 A．n—l C．n(n+1）／2
10．可进行拓扑排序的图只能是 A．有向图 C．有向无环图 11．下列排序方法中稳定的是 A．直接插入排序 C．堆排序 12．下列序列不为堆的是 ．．
A．75，45，65，30，15，25 C．75,65，30,l5，25，45
B．75，65，45，30,25，15 D．75，45,65，25，30，15 B．直接选择排序 D．快速排序 B．无向图 D．无向连通图 B．n(n—1）／2 D．n2
13．对线性表进行二分查找时,要求线性表必须是 A．顺序存储
B．链式存储
2 / 100
C．顺序存储且按关键字有序 D．链式存储且按关键字有序
14．分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的,不同 ．． 的序列是
A．(4，1,2，3,5） C．（4,5,2，1，3)
B．(4,2，3，l,5) D．（4,2，1，5,3)
15．下列关于m阶B树的叙述中，错误的是 ．． A．每个结点至多有m个关键字 B．每个结点至多有m棵子树
C．插入关键字时,通过结点分裂使树高增加 D．删除关键字时通过结点合并使树高降低
非选择题部分
注意事项：
用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。
二、填空题(本大题共10小题，每小题2分,共20分） 16．数据元素之间的逻辑关系称为数据的______结构。 17．在线性表中，表的长度定义为______.
18．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1、2、3、4，为了得到 1、3、4、2的出栈顺序，相应的S和X的操作序列为______。 19．在二叉树中,带权路径长度最短的树称为______。
20．已知广义表G，head（G)与tail（G）的深度分别为4和6，则G的深度是______。 21．一组字符(a,b,c，d）在文中出现的次数分别为（7，6，3，5），字符＇d＇的哈夫曼编码的长度为______.
22．在一个具有n个顶点的无向图中，要连通全部顶点至少需要______条边。 23．直接选择排序算法的时间复杂度是______。
24．对于长度为81的表,若采用分块查找，每块的最佳长度为______. 25．用二叉链表保存有n个结点的二叉树,则结点中有______个空指针域。 三、解答题（本大题共4小题，每小题5分，共20分）
3 / 100
26．假设Q是一个具有11个元素存储空间的循环队列（队尾指针指向队尾元素的下一 个位置，队头指针指向队头元素)，初始状态Q.front=Q.rear=0；写出依次执行 下列操作后头、尾指针的当前值.
a，b,c，d,e,f入队，a,b，c，d出队； (1) Q.front=______；Q.rear=______。 g,h,i,j，k,l入队，e,f,g，h出队; （2) Q.front=______；Q。rear=______。
M，n，o,P入队， i，j,k，l,m出队； （3） Q。front=______；Q。rear=______。
27．已知一个无向图如题27图所示，以①为起点，用普里姆（Prim）算法求其最小生
成树，画出最小生成树的构造过程。
28．用归并排序法对序列 (98，36,—9，0，47，23,1,8）进行排序，问： （1)一共需要几趟归并可完成排序。 （2)写出第一趟归并后数据的排列次序.
29．一组记录关键字(55，76,44，32，64,82,20,16,43)，用散列函数H（key)=key％11将记录 散列到散列表HT[0.。12］中去,用线性探测法解决冲突. （1）画出存入所有记录后的散列表.
(2)求在等概率情况下,查找成功的平均查找长度。
四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．顺序表类型定义如下： ＃ define ListSize 100 typedef struct { int data［ListSize］； int length； ｝SeqList；
4 / 100
阅读下列算法，并回答问题： void f30(SeqList ＊L） ｛ int i,j； i=0;
while(i { for（j=i+1； j〈L—〉length； j++ } L->data[j—1］=L->data[j］； L->length-—； ｝ else i++ ｝ （1)若L-〉data 中的数据为(22，4，63，0,15，29，34，42，3），则执行上述算法后L—〉 data中的数据以及L-〉length的值各是什么？ (2）该算法的功能是什么？ 31。有向图的邻接矩阵类型定义如下： #define MVN 100 ∥ 最大顶点数 typedef int EType； ∥ 边上权值类型 typedef struct{ EType edges[MVN]［MVN］; ∥ 邻接矩阵，即边表 int n; ∥ 图的顶点数 ｝MGraph; ∥ 图类型 例如，一个有向图的邻接矩阵如下所示： 0 1 0 0 01 0 0 0 1A0 1 0 1 0 1 0 0 0 00 0 0 1 1阅读下列算法,并回答问题： 5 / 100 Void f31(MGraph G） { Int i,j,k=0; Step1： for (i=0; i〈G.n; i++） for （j=0； j for （j=0; j〈G.n； j++) { k=0； for （i=0; i〈G。n; j++） if (G。edges［i][j］= =1) k++； printf（“%d } ｝ （1）stepl到step2之间的二重循环语句的功能是什么？ (2)step2之后的二重循环语句的功能是什么? 32．阅读下列算法,并回答问题: void f32(int r[］， int n) { Int i,j; for （i=2;i { r[j+l］=r[j］； j=j—1； ｝ 6 / 100 n\"，k); n”，k）； r[j+l］=r[0]； } } （1)这是哪一种插入排序算法？该算法是否稳定? (2）设置r[0］的作用是什么？ 33．顺序表类型定义如下： typedef int SeqList［100]; 阅读下列算法，并回答问题： void f33(SeqList r, int n） { int a， b,i； if （r［0]〈r［1]) { a=r[0]；b=r[1］； > else { a=r［1]； b=r[0］； ｝ for (i=2;i〈n；i++) if (r[i]〈a) a=r［i]; else if （r[i］〉b） b=r［i]； printf（＂a=%d，b=%d. ｝ （1)给出该算法的功能； (2）给出该算法的时间复杂度。 五、算法设计题（本题10分) 34．二叉树的存储结构类型定义如下 typedef struct node｛ int data； struct node lchild, rchild； } BinNode； typedef BinNode BinTree； 编写递归算法，求只有一个孩子结点的结点总数,并计算这些结点的数据值的和。 ＊＊ ＊ n＂,a，b)； 7 / 100 函数的原型为：void f34(BinTree T， int count, int count和*sum的初值为0。 ＊ ＊ *sum) 8 / 100 9 / 100 10 / 100 2012年1月高等教育自学考试全国统一命题考试 数据结构 试题 课程代码：02331 考生答题注意事项： 1. 本卷所有试卷必须在答题卡上作答。答在试卷和草稿纸上的无效。 2. 第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3. 第二部分为非选择题.必须注明大、小题号，使用0.5毫米黑色字迹笔作答. 4. 合理安排答题空间,超出答题区域无效. 一、单项选择题(本大题共15小题，每小题2分,共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1。每个结点有且仅有一个直接前趋和多个(或无)直接后继（第一个结点除外)的数据结构称 为 A.树状结构 C.线性结构 B。网状结构 D.层次结构 2。某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素,则最节省运算时间的存储结构是 A.单链表 C。仅有头指针的单循环链表 B。双链表 D。仅有尾指针的单循环链表 3。已知一个栈的入栈序列是1,2，3,…，n,其输出序列为pl，p2,p3…。，pn,若p1是n，则pi是 A。i C.n-i+l 4.下面关于串的叙述中,正确的是 A。串是一种特殊的线性表 C.空串就是空白串 B.串中元素只能是字母 D.串的长度必须大于零 11 / 100 B。n-i D。不确定 5.无向完全图G有n个结点，则它的边的总数为 A.n2 C.n(n—1)/2 B.n(n—1) D.（n—1) 6。若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是 A。9 C.15 B。11 D。不确定 7。如图所示，在下面的4个序列中，不符合深度优先遍历的序列是 ．．．A。acfdeb B。aebdfc C。aedfbc D.aefdbc 8.无论待排序列是否有序，排序算法时间复杂度都是O(n2)的排序方法是 A。快速排序 C.冒泡排序 B。归并排序 D。直接选择排序 9。已知二叉排序树G，要输出其结点的有序序列，则采用的遍历方法是 A。按层遍历 C。中序遍历 10.用ISAM和VSAM组织的文件都属于 A。散列文件 C.索引非顺序文件 B。索引顺序文件 D。多关键字文件 B。前序遍历 D。后序遍历 11。对序列(15,9，7，8,20，—1，4）进行排序，第一趟排序后的序列变为（4，9，-1，8，20，7，15），则采用的排序方法是 A.选择 C.希尔 12。当采用分块查找时,数据的组织方式为 A。数据分成若干块，每块内数据有序 B。数据分成若干块，每块中数据个数必须相同 C。数据分成若干块,每块内数据有序，块间是否有序均可 D.数据分成若干块，每块内数据不必有序,但块间必须有序 12 / 100 B.快速 D.冒泡 13.下述编码中不是前缀码的是 A。(00,01，10，11） C.（0,10，110,111） B.（0，1,00,11） D.(1，01，000,001) 14。若一个栈以向量V［1。.n］存储，初始栈顶指针top为n+l，则x进栈的正确操作是 A.top=top—1；V［top］=x C。top=top+1；V[top］=x B。V[top］=x；top=top+1 D。V[top]=x;top=top-1 15.在一个以head为头结点指针的非空单循环链表中，指针p指向链尾结点的条件是 A。p - 〉 data = — 1 C。p — 〉 next - > next=head B。p - 〉 next = NULL D.p - 〉 next = head 二、填空题（本大题共10小题，每小题2分，若有两个空格,每个空格1分，共20分)请在每个空格中填上正确答案。错填、不填均无分。 16。在数据的逻辑结构和存储结构中，与计算机无关的是______. 17。线性表L=（a1，a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。 18。设循环队列的容量为50（序号从0到49),现经过一系列的入队和出队运算后，有①front=11，rear=29；②front=29，rear=11；在这两种情况下,循环队列中的元素个数分别是______和______。 19.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______. 20.已知三对角矩阵A[10］[10]的每个元素占2个单元,现将其三条对角线上的元素逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A［6］[7] 的地址为______. 21.若以(4,5，6，7,8）作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。 22.有向图G如图所示，它的两个拓扑排序序列分别为______和______. 13 / 100 23。一组记录的关键字为(46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为______。 24。已知广义表A=（x，((a,b),c,）)，函数head(head（tail(A)））的运算结果是______。 25.索引顺序文件既可以顺序存取，也可以______。 三、解答题（本大题共4小题，每小题5分，共20分） 26。对关键字序列（26，18，60，14,7，45，13，32)进行降序的堆排序，写出构建的初始堆(小根堆）及前两趟重建堆之后序列状态. 初始堆： 第一趟： 第二趟： 27。设散列函数为H （key）=key % 11，散列地址空间为0··10，对关键字序列(27，13，55，32，18，49，24，38，43）用线性探查法解决冲突，构建散列表.现已有前4个关键字构建的散列表如下所示,请将剩余5个关键字填入表中相应的位置。 28。已知一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG和CBDAEGF，请画出此二叉树,并给出后序遍历序列。 29.已知如图所示的带权无向图,请画出用普里姆算法从顶点1开始的最小生成树的构造过程。 四、算法阅读题（本大题共4小题，每小题5分,共20分） 30.阅读下列算法，并回答下列问题: (1）简述该算法的功能; 14 / 100 (2)写出分别输入字符串：”abcba\"和\"abcbde”,调用算法函数的返回值。 int symmetry（void） ｛ int i=0,j，k；. char str[80］； SeqStack s； InitStack（＆s)； gets （str)； while （str［i]！= ’＼0’) i++; for (j=0;jreturn 0; return 1； } （1) （2） 31。下列算法是利用二分查找方法在递减有序表R中插入元素x，并保持表R的有序性。．．请在空缺处填入适当的内容，使其成为一个完整的算法。 typedef struct { KeyType key; InfoTyep otherinfo； ｝ RecType; typedef RecType SeqList [Maxlen］ void BinInsert（SeqList R,int ＊n,RecType x） ｛ int low=1，high=＊n; int mid,i； 15 / 100 while （low〈=high） ｛ mid=（low+high)/2； if （x.key>R［mid］.key) （1） ； else (2) ; } for （i=＊n；i>=low；i—-) R［i+1]=R［i］； （3) ; ++(*n)； } (1） (2) (3） 32.阅读下列算法，并回答下列问题： (1）简述该算法中标号s1所指示的循环语句的功能； (2）简述该算法中标号s2所指示的循环语句的功能。 LinkList Insertmnode（LinkList head，char x,int m） { LinkNode＊p,＊q，*s； int i; char ch； p=head->next； s1：while （p＆＆p->data！=x) p=p—〉next； if (p==NULL）printf(”error\\n”）; else ｛ q=p—〉next; s2： for（i=1；i〈=m;i++) { s=（LinkNode ＊) malloc(sizeof（LinkNode))； 16 / 100 scanf(”％c\"，&ch)； s—>data=ch； p-〉next=s; p=s； ｝ p-〉next=q； } return head； ｝ (1） （2） 33.阅读下列算法，并回答下列问题： (1)该算法采用的是何种排序方法？ (2）算法中的R［n+1］的作用是什么？ typedef struct ｛ KeyType key； InfoType otherinfo； }RecType； typedef RecType SeqList［MaxLen］； void sort(SeqList R，int n） { //n for （k=n-1；k>=1；k-—） if （R[k]。key〉R[k+l］。key) { R［n+1]=R[k]； for (i=k+1；R［i]。key〈R［n+1］.key；i++) R［i—1]=R［i］; R［i-l]=R［n+1]; 17 / 100 } ｝ （1） (2) 五、算法设计题（本题10分) 34.假设以单链表表示线性表,单链表的类型定义如下： typedef struct node { DataType data; Struct node *next； } LinkNode，* LinkList； 编写算法，在一个头指针为head且带头结点的单链表中，删除所有结点数据域值为x的结点。函数原型为：LinkList delnode （LinkList head，DataType x） 18 / 100 19 / 100 20 / 100 全国2011年10月高等教育自学考试 数据结构试题 课程代码：02331 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内.错选、多选或未选均无分。 1、在数据的逻辑结构中，树结构和图结构都是（ ） A。非线性结构 C。动态结构 B.线性结构 D.静态结构 2。在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（ ) A。O(1） C.O(n） B。Ｏ（log n） D.O（n2) 3.指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表,应执行的操作为（ ） A.p1－＞next=p2－＞next；p2－＞next=p1－＞next； B。 p2－＞next=p1－＞next；p1－＞next=p2－＞next; C. p=p2－＞next; p1－＞next=p;p2－＞next=p1－＞next; D。 p=p1－＞next; p1－＞next= p2－＞next；p2－＞next=p； 4.设栈的初始状态为空，入栈序列为1，2，3,4，5，6，若出栈序列为2，4,3,6，5，1，则操作过程中栈中元素个数最多时为( ） A。2个 C。4个 5。队列的特点是（ ） A.允许在表的任何位置进行插入和删除 B。只允许在表的一端进行插入和删除 C。允许在表的两端进行插入和删除 D。只允许在表的一端进行插入，在另一端进行删除 6.一个链串的结点类型定义为 ﹟define NodeSize 6 21 / 100 B.3个 D。6个 typedef struct node{ char data[NodeSize］； struct node＊next; }LinkStrNode; 如果每个字符占1个字节,指针占2个字节，该链串的存储密度为（ ） A。1/3 C。2/3 B.1/2 D.3/4 7。广义表A=（a，B,（a，B，（a，B,……）））的长度为（ ） A.1 C。3 B.2 D.无限值 8。已知10×12的二维数组A，按“行优先顺序”存储，每个元素占1个存储单元，已知A[1］［1］的存储地址为420，则A［5]［5]的存储地址为（ ) A。470 C.472 B.471 D.473 9.在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为( ） A。12 C。18 B.16 D.20 10.在带权图的最短路径问题中,路径长度是指( ) A。路径上的顶点数 C.路径上的顶点数与边数之和 B.路径上的边数 D。路径上各边的权值之和 11.具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（ ） A。e C.n2—2e B.2e D。n2-1 12.要以O（n log n)时间复杂度进行稳定的排序，可用的排序方法是（ ） A.归并排序 C.堆排序 B.快速排序 D。冒泡排序 13。若希望在1000个无序元素中尽快求得前10个最大元素,应借用（ ） A。堆排序 C.冒泡排序 B.快速排序 D.归并排序 22 / 100 14。对有序表进行二分查找成功时，元素比较的次数（ ) A.仅与表中元素的值有关 C.仅与被查元素的值有关 15。散列文件是一种（ ） A。顺序存取的文件 C。索引存取的文件 B。随机存取的文件 D.索引顺序存取的文件 B.仅与表的长度和被查元素的位置有关 D.仅与表中元素按升序或降序排列有关 二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上正确答案.错填、不填均无分. 16.若一个算法中的语句频度之和为T(n）=3n3—200nlog2n+50n,则该算法的渐近时间复杂度为__________. 17。在单链表中，除了第1个元素结点外,任一结点的存储位置均由_____________指示。 18。栈的修改是按__________的原则进行. 19。字符串中任意个连续的字符组成的子序列称为该串的__________. 20。假设一个10阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，若矩阵中的第一个元素a11在B中的存储位置k=0,则元素a55在B中的存储位置k=__________。 21.在一棵具有n个结点的严格二叉树中,度为1的结点个数为__________。 22.对于稀疏图，采用__________表示法较为节省存储空间. 23。在排序过程中,如果_____________，则称其为外部排序. 24。设有一组记录的关键字为{19，14，23,1，68，12，10，78，25｝，用链地址法构造散列表,散列函数为h（key）=key％11，散列地址为1的链中有__________个记录。 25。多关键字文件的特点是除主文件和主索引外，还建有__________. 三、解答题(本大题共4小题，每小题5分，共20分） 26.对于下列稀疏矩阵（注：矩阵元素的行列下标均从1开始) 008000071050006000000 0029（1）画出三元组表； 23 / 100 (2)画出三元组表的行表。 (1） (2) 27。已知一个森林的前序遍历序列为CBADHEGF，后序遍历序列为ABCDEFGH. （1）画出该森林; （2）画出该森林所对应的二叉树。 (1） （2) 28。对关键字序列（429，653，275，897，170，908，473,256，726）进行基数排序，写出每一趟的排序结果。 29。对下列关键字序列 （87，25,310，08，27，132,68，96,187，133，70，63,47,135） 构造散列表，假设散列函数为h（key）=key%13，用拉链法解决冲突。 （1)画出该散列表； （2）求等概率情况下查找成功的平均查找长度ASL; （3)写出删除值为70的关键字时所需进行的关键字比较次数. (1) （2) (3) 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30.阅读下列算法，并回答问题： (1）假设L=（3，7，7，11,20，20，20，51，51），写出执行函数f30（&L）后的L； (2)简述f30的功能。 void f30（SeqList＊L） { ∥L为非空的有序表 int i=1,k=0； while(i＜L－＞length) ｛ if(L－＞data［i］!=L－＞data［k］) 24 / 100 L－＞data［++k］=L－＞data［i］; i++； ｝ L－＞length=k+1； ｝ (1） （2) 31。阅读下列算法，并回答问题: （1）假设栈S=（3,8，6，2,5），其中5为栈顶元素,写出执行函数f31(＆S)后的S; （2）简述函数f31的功能. void f31（Stack ＊S）{ Queue Q；InitQueue（&Q); while（!StackEmpty(S）） EnQueue(&Q，Pop(＆S)）; while(！QueueEmpty(Q）) Push(＆S,DeQueue（&Q））； ｝ （1） （2） 32。假设具有n个结点的完全二叉树顺序存储在向量BT[1.. n]中，阅读下列算法，并回答问题： （1）若向量BT为： A B C D E F G 1 2 3 4 5 6 7 画出执行函数f32（BT,7，1)的返回结果； （2)简述函数f32的功能。 BinTree f32（DataType BT[],int n，int i) { 25 / 100 BinTree p; if (i＞n） return NULL; p=（BinTNode*）malloc（sizeof(BinTNode)）; p－＞data=BT[i］; p－＞lchild=f32(BT,n，i＊2）; p－＞rchild=f32(BT,n,i*2+1）; return p； } （1) (2） 33.已知有向图的邻接表和邻接矩阵定义如下: ﹟define MaxNum 50 typedef struct node ｛ int adjvex； struct node *next; } EdgeNode; typedef struct｛ char vertex； EdgeNode *firstedge； ｝ VertexNode； typedef struct { VertexNode adjlist ［MaxNum］; int n,e； ｝ ALGraph; typedef struct{ char vertex［MaxNum]； int adjmatrix ［MaxNum］［MaxNum］； int n，e; ｝ AMGraph； 26 / 100 ∥邻接矩阵 ∥顶点表 ∥邻接表 ∥图中当前顶点数和边数 ∥邻接表描述的图 ∥顶点域∥边表头指针∥顶点表结点结构 ∥邻接点域 ∥图的最大顶点数 ∥链指针域 ∥边表结点结构∥图中当前顶点数和边数 ∥邻接矩阵描述的图下列算法是将邻接表描述的图G1改为邻接矩阵描述的图G2，在空白处填上适当内容使算法完整: void f33（ALGraph G1，AMGraph ＊G2） { int i, j； EdgeNode *p; G2－＞n=G1。n; G2－＞e= （1) ； for （i=0; i＜G1。n; i++） { G2－＞vertex［i]= （2) ; p=G1。adjlist［i].firstedge； for （j=0； j＜G1。n; j++） G2－＞adjmatrix[i]［j］=0; while （p) ｛ G2－＞adjmatrix［i]［p－＞adjvex]=1; （3） ; } } ｝ （1) (2) （3） 五、算法设计题（本题10分) 34.设顺序表Ｌ是一个递增有序表。编写算法,要求利用二分查找法确定插入位置，将元素ｘ插入到Ｌ中,使Ｌ保持有序。 27 / 100 28 / 100 29 / 100 30 / 100 31 / 100 全国2011年1月自考数据结构试题及答案 课程代码：02331 一、单项选择题(本大题共15小题,每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内.错选、多选或未选均无分。 1。下列选项中与数据存储结构无关的术语是（ ） A。顺序表 C.链队列 B。链表 D.栈 2。将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（ ) A.n—1 C.2n-1 B.n D.2n 3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（ ） A.rear=（rear—1)％m； C。front=（front-1)％m; B.front=（front+1)%m; D。rear=（rear+1)%m； 4。递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（ ) A。堆栈 C。队列 B。多维数组 D.线性表 5。设有两个串p和q,其中q是p的子串，则求q在p中首次出现位置的算法称为( ) A.求子串 C.串匹配 B。串联接 D.求串长 6.对于广义表A，若head(A)等于tail(A）,则表A为（ ) A。( ） C。(（ ），( )） B.(( )) D。(（ ),（ ),（ ）) 7。若一棵具有n(n〉0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是 ( ） A.结点均无左孩子的二叉树 C。高度为n的二叉树 B。结点均无右孩子的二叉树 D.存在度为2的结点的二叉树 32 / 100 8。若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4,则该二叉树叶子结点的个数是（ ） A.4 C.7 9.下列叙述中错误的是（ ) A。图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次 B.图的遍历可以采用深度优先遍历和广度优先遍历 C。图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程 10。已知有向图G=（V，E),其中V=｛V1，V2，V3，V4},E={〈V1,V2〉， 11.平均时间复杂度为O（n log n）的稳定排序算法是( ) A。快速排序 C。归并排序 B。堆排序 D.冒泡排序 12。已知关键字序列为（51，22,83，46，75，18,68,30），对其进行快速排序，第一趟划分完成后的关键字序列是（ ） A。(18，22，30，46,51,68，75，83) C.（46,30,22，18,51,75,68，83） B。(30，18,22,46,51,75,83,68) D。(30,22，18，46,51,75,68，83) 13.某索引顺序表共有元素395个，平均分成5块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是( ） A.43 C。198 B.79 D.200 14。在含有10个关键字的3阶B-树中进行查找，至多访问的结点个数为（ ） A。2 C.4 B.3 D。5 15.ISAM文件系统中采用多级索引的目的是( ) A.提高检索效率 B.提高存储效率 33 / 100 C.减少数据的冗余 D。方便文件的修改 二、填空题（本大题共10小题，每小题2分,共20分) 请在每小题的空格中填上正确答案.错填、不填均无分。 16。数据结构由数据的逻辑结构、存储结构和数据的____________三部分组成. 17。在单链表中某结点后插入一个新结点,需要修改_______________个结点指针域的值。 18.设栈S的初始状态为空，若元素a、b、c、d、e、f依次进栈,得到的出栈序列是b、d、c、f、e、a，则栈S的容量至少是________________. 19。长度为零的串称为________________。 20。广义表G=（a，b，(c，d，(e，f)),G）的长度为________________。 21。一棵树T采用孩子兄弟链表存储，如果树T中某个结点为叶子结点，则该结点在二叉链表中所对应的结点一定是________________. 22。一个有n个顶点的无向连通图,最少有________________条边. 23.当待排关键字序列基本有序时,快速排序、简单选择排序和直接插入排序三种排序方法中,运行效率最高的是________________。 24.在一棵深度为h的具有n个结点的二叉排序树中，查找任一结点的最多比较次数是______________。 25.不定长文件指的是文件的____________大小不固定。 三、解答题（本大题共4小题，每小题5分，共20分) 26。已知一棵二叉排序树(结点值大小按字母顺序）的前序遍历序列为EBACDFHG， 请回答下列问题： （1）画出此二叉排序树; （2)若将此二叉排序树看作森林的二叉链表存储，请画出对应的森林. 27。已知有向图的邻接表如图所示,请回答下面问题： （1）给出该图的邻接矩阵； (2)从结点A出发，写出该图的深度优先遍历序列. 28。已知待排记录的关键字序列为｛25，96,11，63，57，78,44}，请回答下列问题： 34 / 100 （1)画出堆排序的初始堆（大根堆)； （2）画出第二次重建堆之后的堆。 29.已知关键字序列为（56，23，41，79，38，62,18），用散列函数H（key）=key%11将其散列到散列表HT[0。。10］中，采用线性探测法处理冲突.请回答下列问题： （1）画出散列存储后的散列表： (2）求在等概率情况下查找成功的平均查找长度。 四、算法阅读题（本大题共4小题，每小题5分，共20分) 30。阅读下列程序. void f30（int A[]， int n） ｛ int i，j，m； for (i=1；i〈n；i++) for （j=0；j〈i;j++) { m=A［i＊n+j］; A［i＊n+j]=A［j＊n+i］； A[j*n+i］=m; ｝ } 回答下列问题: 1 2 3(1)已知矩阵B= 4 5 6，将其按行优先存于一维数组A中，给出执行函数调 7 8 9用f30(A，3）后矩阵B的值； (2)简述函数f30的功能。 31。假设以二叉链表表示二叉树，其类型定义如下： typedef struct node { char data; 35 / 100 struct node＊Ichild， ＊rchild； ∥左右孩子指针 ｝ *BinTree； 阅读下列程序。 void f31（BinTree T） ｛ InitStack(S）; ∥ 初始化一个堆栈S while （T ｜| !StackEmpty（S) ｛ while （T) ｛ Push(S，T)； T=T—〉lchild； ｝ if (！StackEmpty(S）) { T=Pop（S)； printf(“％c”，T->data)； T=T-〉rchild； } ｝ ｝ 回答下列问题: (1)已知以T为根指针的二叉树如图所示, 请写出执行f31（T）的输出结果： (2）简述算法f31的功能。 32.阅读下列程序。 void f32（int A［]，int n） ｛ int i,j,m=l，t； for （i=0； i〈n—l＆＆m; i++) ｛ for (j=0； j printf(“％d ”,A[j])； printf（“＼n”）； m=0: for (j=1； j t=A［j—l]; A[j—1］=A[j］; A[j］=t； m=1； } } ｝ 回答问题： 已知整型数组A[ ］=｛34，26,15,89,42｝，写出执行函数调用f32(A,5）后的输出结果。 33.已知顺序表的表结构定义如下: ＃define MAXLEN 100 typedef int KeyType； typedef struct ｛ KeyType key; InfoType otherinfo; ｝ NodeType； typedef NodeType SqList[MAXLEN］; 阅读下列程序。 Int f33(SqList R,NodeType X， int p, int q) { int m; if （p〉q) return -1； m=(p+q)／2； if (R[m]。key==X.key） return m； 37 / 100 if （R[m].key〉X。key) return f33（R,X，p，m-l); else return f33(R,X，m+l,q）; } 请回答下列问题： （1）若有序的顺序表R的关键字序列为(2，5，13,26，55，80,105),分别写出X。key=18和X。key=26时,执行函数调用f33(R，X,0,6）的函数返回值。 （2)简述算法f33的功能。 五、算法设计题(本题10分） 34.假设用带头结点的单循环链表表示线性表，单链表的类型定义如下： typedef struct node { int data; struct node＊next； }LinkNode，＊LinkList； 编写程序，求头指针为head的单循环链表中data域值为正整数的结点个数占结点总数的比例，若为空表输出0，并给出所写算法的时间复杂度。函数原型为： float f34(LinkList head)： 38 / 100 39 / 100 40 / 100 41 / 100 42 / 100 全国2010年10月高等教育自学考试 数据结构试题 课程代码:02331 一、单项选择题（本大题共15小题,每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.数据的四种存储结构是( ) A。顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构 2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中,应选择的存储结构是（ ） A。无头结点的单向链表 C。带头结点的双循环链表 B.带头结点的单向链表 D。带头结点的单循环链表 3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( ) A.head=NULL C。head！=NULL B.head->next=NULL D.head—>next！=head 4.若元素的入栈顺序为1,2，3..。。，n，如果第2个出栈的元素是n,则输出的第i(1<=i<=n）个元素是( ） A。n—i C.n—i+2 5.串匹配算法的本质是( ） A。串复制 C.子串定位 B.串比较 D.子串链接 B。n-i+l D。无法确定 6。设有一个10阶的对称矩阵A,采用行优先压缩存储方式，a11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a85的地址为（ ） A。13 C。33 B.18 D.40 43 / 100 7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( ) A.树中没有度为2的结点 C。树中非叶结点均只有左子树 B.树中只有一个根结点 D.树中非叶结点均只有右子树 8。若根结点的层数为1，则具有n个结点的二叉树的最大高度是（ ） A。n C. +1 B. D。n/2 9。在图G中求两个结点之间的最短路径可以采用的算法是（ ） A。迪杰斯特拉(Dijkstra）算法 C.普里姆（Prim）算法 B。克鲁斯卡尔(Kruskal)算法 D。广度优先遍历（BFS)算法 10.下图G=(V,E)是一个带权连通图，G的最小生成树的权为( ） A。15 B。16 C。17 D.18 11。在下图中，从顶点1出发进行深度优先遍历可得到的序列是( ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7 12。如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( ） A。不稳定的 C.基于交换的 B。稳定的 D。基于选择的 13.设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11， 10， 9）,用散列函数H（key)=key％13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为( ） A。1 C.3 44 / 100 B.2 D。4 14。已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( ) 15.若需高效地查询多关键字文件,可以采用的文件组织方式为（ ） A。顺序文件 C.散列文件 B。索引文件 D。倒排文件 二、填空题（本大题共10小题，每小题2分,共20分） 请每小题的空格中填上正确答案.错填、不填均无分。 16.下面程序段的时间复杂度为___________。 sum=1； for（i=0；sum 17.已知链表结点定义如下： typedef struct node｛ char data[16］； struct node ＊next； } LinkStrNode； 如果每个字符占1个字节,指针占4个字节，则该链表的存储密度是___________。 18.使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8,rear=7，则队列中的元素个数为___________。 45 / 100 19。3个结点可以组成___________种不同树型的二叉树。 20。用5个权值{3, 2，4，5,1}构造的哈夫曼（Huffman）树的带权路径长度是___________。 21。若无向图G中有n个顶点m条边，采用邻接矩阵存储,则该矩阵中非0元素的个数为___________. 22。影响排序效率的两个因素是关键字的___________次数和记录的移动次数。 23。对任一m阶的B树，每个结点中最多包含___________个关键字。 24.若两个关键字通过散列函数映射到同一个散列地址,这种现象称为___________。 25。如果要为文件中的每个记录建立一个索引项，则这样建立的索引表称为___________. 三、解答题（本大题共4小题，每小题5分，共20分) 26.要在[0.。n-l]的向量空间中建立两个栈stackl和stack2,请回答： （1)应该如何设计这两个栈才能充分利用整个向量空间？ (2）若stackl的栈顶指针为topl，stack2的栈顶指针为top2，如果需要充分利用整个向量空间，则： 栈stackl空的条件是：___________； 栈stack2空的条件是：___________； 栈stackl和栈stack2满的条件是：___________. 27.已知广义表如下： A=（B,y） B=(x，L） L=（a，b) 要求: (1)写出下列操作的结果 tail（A）=_______________. head(B)=______________。 (2)请画出广义表A对应的图形表示。 28。已知二叉树如下： 46 / 100 请画出该二叉树对应的森林。 29.请回答下列问题： (1)英文缩写DAG的中文含义是什么？ （2)请给出下面DAG图的全部拓扑排序。 四、算法阅读题(本大题共4小题，每小题5分,共20分） 30。已知线性表（a1,a2,a3..。,an)按顺序存放在数组a中，每个元素均为整数，下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如,有7个整数的原始序列为(x,x,—x,—x,x,x，—x),变换后数组中保存的序列是（-x,-x,—x,x,x,x,x）.请在程序处填入合适的内容,使其成为完整的算法。 f30（int a[］，int n) { int k，m,temp； m= （1） ； while （a［m］<0 &＆m〈n) m= （2） ； k=m； while （k { temp=a［k］； a［k］=a[m］; a［m］= (4) ； m= (5） ； ｝ } ｝ （1) (2) (3) （4） (5） 31。阅读下列程序，并回答问题： ＃include〈stdio.h〉 substr（char＊t,char*s，int pos,int len) { while（len>0＆&＊s） ｛ *t=*（s+pos—l); t++；s++;len-—; } ＊t=’\\0’； } char ＊f31(char*s） { char t［100］； if (strlen(s)=1） return s; substr(t,s，1,1）； substr（s,s，2，strlen（s)—1)； f31（s)； return strcat（s，t）; 48 / 100 ｝ main( ） ｛ char str[100］= ''String’'; printf(’’％s\\n'',f31（str))； ｝ （1）请写出执行该程序后的输出结果； (2）简述函数f31的功能。 32。下面程序实现插入排序算法。 typedef struct｛ int key; Info otherinfo； }SeqList; void InsertSort（SeqList R[］,int n) ｛/* 待排序列保存在R[1。.n]中＊/ SeqList x； int i，j,k，lo,hi,mi; for （i=2；i<=n；i++) ｛ （1） ； lo=1； hi=i-l; while (lo<=hi） ｛ mi=(lo+hi）/2; if （ （2） ) break； if (R［mi］。key>x。key) hi=mi—l； else lo=mi+l； ｝ if (mi=lo) k=i - mi； 49 / 100 else k=i — mi—1; for （j=0；j 在空白处填写适当的内容，使该程序功能完整。 （1） (2) （3） 33.设有单链表类型定义如下: typedef struct node { int data； struct node ＊next; } ＊LinkList； 阅读下列算法，并回答问题： void f33(LinkList head， int A, int B） { LinkList p=NULL; While （head ！=NULL) ｛ if (head-〉data>A＆＆head-〉data〈B） p=head； head=head—>next; ｝ if (p ！=NULL) printf(”％d\\n\"，p—>data)； ｝ (1）已知链表h如下图所示，给出执行f33（h，5，8)之后的输出结果； 50 / 100 （2）简述算法f33的功能。 五、算法设计题（本题10分） 34。已知二叉树的定义如下： typedef struct node{ int data; struct node *lchild, *rchild; ｝＊Bitptr; 编写递归算法求二叉树的高度。函数原型为：int f34(Bitptr t)； 2010年10月全国自考数据结构试题 课程代码:02331 一、单项选择题（本大题共15小题，每小题2分，共30分) 1．数据的四种存储结构是（A） A。顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C。集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构 2．若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是（C) A。无头结点的单向链表 C。带头结点的双循环链表 B.带头结点的单向链表 D。带头结点的单循环链表 3．若带头结点的单链表的头指针为head，则判断链表是否为空的条件是(B） A。head=NULL C.head!=NULL B。head—>next=NULL D.head-〉next！=head 4．若元素的入栈顺序为1，2，3...。，n，如果第2个出栈的元素是n，则输出的第i(1〈=i<=n）个元素是(D） A。n-i B.n—i+l C.n—i+2 51 / 100 D。无法确定 5．串匹配算法的本质是（C） A.串复制 B。串比较 C。子串定位 D.子串链接 6．设有一个10阶的对称矩阵A,采用行优先压缩存储方式,a11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a85的地址为（C） A。13 B.18 C.33 D.40 7．若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是(B） A。树中没有度为2的结点 C.树中非叶结点均只有左子树 B.树中只有一个根结点 D。树中非叶结点均只有右子树 8．若根结点的层数为1，则具有n个结点的二叉树的最大高度是（A) A.n B.log2n C。log2n+1 9．在图G中求两个结点之间的最短路径可以采用的算法是(A） A.迪杰斯特拉（Dijkstra）算法 C.普里姆(Prim）算法 B.克鲁斯卡尔（Kruskal）算法 D。广度优先遍历（BFS)算法 D。n/2 10．下图G=(V，E）是一个带权连通图，G的最小生成树的权为(D） A。15 B.16 C.17 D.18 11．在下图中，从顶点1出发进行深度优先遍历可得到的序列是（B） A.1 2 3 4 5 6 7 B。1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D。1 2 4 6 5 3 7 12．如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是(B) A。不稳定的 B.稳定的 C.基于交换的 D.基于选择的 13．设有一组关键字（19， 14， 23， 1，6,20， 4，27， 5，11， 10， 9），用散列函 52 / 100 数H（key）=key%13构造散列表,用拉链法解决冲突，散列地址为1的链中记录个数为(C) A。1 B.2 C。3 D.4 14．已知二叉树结点关键字类型为字符,下列二叉树中符合二叉排序树性质的是(D) 15．若需高效地查询多关键字文件，可以采用的文件组织方式为（D) A.顺序文件 B。索引文件 C.散列文件 D。倒排文件 二、填空题(本大题共10小题，每小题2分，共20分） 16．下面程序段的时间复杂度为（O(n））。 sum=1； for（i=0;sum〈n；i++) sum+=1； 17．已知链表结点定义如下： typedef struct node{ char data［16］； struct node ＊next； ｝ LinkStrNode； 如果每个字符占1个字节，指针占4个字节,则该链表的存储密度是（0。8)。 18．使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满,约定队头指针front等于队尾指针rear时表示队空。若为front=8,rear=7,则队列中的元素个数为（99）. 53 / 100 19．3个结点可以组成（5）种不同树型的二叉树。 20．用5个权值｛3, 2，4，5，1｝构造的哈夫曼（Huffman)树的带权路径长度是（33）。 21．若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为(2m）。 22．影响排序效率的两个因素是关键字的（比较)次数和记录的移动次数。 23．对任m阶的B树,每个结点中最多包含（m—1）个关键字。 24．若两个关键字通过散列函数映射到同一个散列地址，这种现象称为（冲突）. 25．如果要为文件中的每个记录建立一个索引项，则这样建立的索引表称为(稠密索引）. 三、解答题（本大题共4小题，每小题5分，共20分） 26．要在[0。。n—l]的向量空间中建立两个栈stackl和stack2，请回答： (1）应该如何设计这两个栈才能充分利用整个向量空间？ (2）若stackl的栈顶指针为topl,stack2的栈顶指针为top2，如果需要充分利用整个向量空间，则： 栈stackl空的条件是：（); 栈stack2空的条件是：（）; 栈stackl和栈stack2满的条件是:（）。 答：(1)采用双向栈的形式，stack1的栈底设置在下标为0的元素上,stack2的栈底设置在下标为n-1的元素上。 （2)top1=-1，top2=n，top1—1=top2 27．已知广义表如下： A=（B,y）,B=(x，L）,L=(a,b），要求： （1）写出下列操作的结果： tail(A)=((y））。head(B)=（x）。 （2)请画出广义表A对应的图形表示. 28．已知二叉树如下： 答:ABxaLb y 54 / 100 abe 请画出该二叉树对应的森林. 答: 29．请回答下列问题： (1)英文缩写DAG的中文含义是什么?(2）请给出下面DAG图的全部拓扑排序。 cghjdkf 答：(1）有向无环图 （2）abdcefg，abdcfeg，adbcefg,adbcfeg 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．已知线性表（a1，a2,a3.。。,an)按顺序存放在数组a中，每个元素均为整数，下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如，有7个整数的原始序列为(x,x,-x,—x,x，x,-x)，变换后数组中保存的序列是(-x，—x，—x,x,x，x，x）。请在程序处填入合适的内容，使其成为完整的算法。 f30（int a[］,int n）｛ int k，m,temp； m= （1）; while （a［m]〈0 ＆＆m〈n） m= （2)； k=m; while （k while(a［k]>=0&＆k〈n） k= （3）； if（k } } 答：（1)0 （2)m+1 (3）k+1 (4）temp (5)m+1 31．阅读下列程序,并回答问题： #include〈stdio.h〉 substr（char＊t,char*s,int pos,int len)｛ while(len>0＆&*s）｛ *t=＊（s+pos-l）； t++;s++;len——； ｝ ＊t=’\\0'； ｝ char *f31（char＊s){ char t[100]; if (strlen（s)=1） (1)请写出执行该程序后的输出结果； (2)简述函数f31的功能。 答:(1) ’’gnirtS'’ (2）将字符串s中的字符倒置. 32．下面程序实现插入排序算法. typedef struct{ int key； Info otherinfo; ｝SeqList; void InsertSort（SeqList R［］,int n）｛ /*待排序列保存在R［1。.n］中*/ SeqList x； int i,j，k，lo，hi,mi； return s； substr(t,s,1,1）; substr（s，s,2，strlen(s）—1）； f31（s）； return strcat(s，t); ｝ main（ ){ char str［100］= ''String'’； printf(’’％s\\n’',f31（str)）； } for (i=2；i〈=n；i++）{ (1）； lo=1; hi=i—l; while(lo<=hi){ mi=(lo+hi）/2; if （ （2）） break; if （R［mi］。key〉x。key) hi=mi—l；56 / 100 else lo=mi+l; } if（mi=lo） k=i—mi； else k=i—mi—1； for (j=0;j 在空白处填写适当的内容，使该程序功能完整。 (3）； 答:（1）x=R［i］ (2）R[mi］.key==x。key 57 / 100 3) R［i—j]=R[i-j—1] （ 33．设有单链表类型定义如下: typedef struct node ｛ int data; struct node *next; ｝ *LinkList; 阅读下列算法,并回答问题： void f33(LinkList head, int A, int B）｛ LinkList p=NULL； while （head !=NULL）{ if (head-〉data>A&＆head-〉data head=head—〉next; ｝ if (p !=NULL) printf（\"%d\\n\ ｝ (1）已知链表h如下图所示,给出执行f33(h，5,8)之后的输出结果; (2）简述算法f33的功能。 答：(1）7 （2）输出链表h中（若存在）最后一个大于A到小于B的值。 五、算法设计题(本题10分） 34.已知二叉树的定义如下: typedef struct node{ int data; struct node *lchild， *rchild； ｝*Bitptr； 编写递归算法求二叉树的高度.函数原型为:int f34（Bitptr t）; 答： int f34（Bitptr t）｛ if（!t） return 0； lh=f34(t->lchild); rh=f34（t-〉rchild）； return lh〉rh？lh+1:rh+1 58 / 100 全国2010年1月高等教育自学考试 数据结构试题 课程代码:02331 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．若一个算法的时间复杂度用T(n)表示，其中n的含义是( ） A．问题规模 C．循环层数 2．具有线性结构的数据结构是（ ） A．树 C．栈和队列 B．图 D．广义表 B．语句条数 D．函数数量 3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ ） A．O（1) C．O(n) B．O(m） D．O（m+n) 4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是( ） A．2个 C．4个 B．3个 D．6个 5．假设以数组［A60]存放循环队列的元素，其头指针是front=47,当前队列有50个元素,则队列的尾指针值为（ ） A．3 C．50 B．37 D．97 6．若栈采用链式存储结构,则下列说法中正确的是（ ) A．需要判断栈满且需要判断栈空 B．不需要判断栈满但需要判断栈空 C．需要判断栈满但不需要判断栈空 D．不需要判断栈满也不需要判断栈空 7．若串str=”Software”,其子串的数目是（ ） A．8 C．36 B．9 D．37 8．设有一个10阶的下三角矩阵A,采用行优先压缩存储方式，all为第一个元素，其存储地址为1000,每个元素占一个地址单元,则a85的地址为 （ ) 59 / 100 A．1012 C．1032 9．允许结点共享的广义表称为（ ） A．纯表 C．递归表 B．1017 D．1039 B．线性表 D．再入表 10．下列数据结构中,不属于二叉树的是（ ） A．B树 C．二叉排序树 B．AVL树 D．哈夫曼树 11．对下面有向图给出了四种可能的拓扑序列，其中错误的是( ) ．． A．1,5,2，6,3，4 C．5,1，6,3,4，2 B．1,5,6,2，3,4 D．5，1，2,6，4，3 12．以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是( ） A．v1，v2,v3,v4，v5,v6，v7 C．v1，v2，v3，v4，v7，v5，v6 13．下列排序算法中不稳定的是（ ) A．快速排序 C．冒泡排序 B．归并排序 D．直接插入排序 B．v1，v2,v5,v4，v3，v7，v6 D．v1，v2，v5，v6,v7,v3，v4 14．一个有序表为（1，3，9，12，32，41，45,62,75，77，82，95，100)，当采用折半查找方法查找值32时，查 找成功需要的比较次数是( ) A．2 C．4 B．3 D．8 15．采用ISAM组织文件的方式属于（ ） A．链组织 C．散列组织 B．顺序组织 D．索引组织 60 / 100 二、填空题(本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．数据元素及其关系在计算机存储器内的表示称为_________。 17．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是_________。 18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_________。 typedef struct{ DataType data［100］； int top； }SeqStack; DataType f18（SeqStack*S) { if(StackEmpty(S）） Error（”Stack is empty”）； return S-〉data［S-〉top］； } 19．在串匹配中,一般将主串称为目标串，将子串称为_________。 20．已知广义表C=（a(b，c)，d)，则：tail(head（tail(C)))= _________。 21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为_________。 22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是_________。 23．对序列{55,46,13，05，94，17，42｝进行基数排序，第一趟排序后的结果是_________。 24．高度为3的3阶B-树最少的关键字总数是_________。 25．VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是_________。 三、解答题（本大题共4小题，每小题5分，共20分) 26．假设二叉树的RNL遍历算法定义如下： 若二叉树非空,则依次执行如下操作： （1）遍历右子树； （2）访问根节点； 61 / 100 (3）遍历左子树. 已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。 27．已知一个无向图G=（V，E)，其中V=｛A，B，C,D，E，F｝，邻接矩阵表示如下所示。 请回答下列问题: (1)请画出对应的图G。 （2)画出图G的邻接表存储结构。 28．已知一组待排记录的关键字序列为（16，12，18，60，15，36，14，18,25，85)，用堆排序方法建小根堆，请 给出初始建堆后的序列. 29．已知一棵二叉排序树如图所示. 请回答下列问题： (1)画出插入元素23后的树结构； （2）请画出在原图中删除元素57后的树结构. 四、算法阅读题（本大题共4小题，每小题5分，共20分) 30．已知下列程序，Ls指向带头结点的单链表. Typedefstruct node { DataType data； struct node ＊ next; ｝ * LinkList; void f30( LinkList Ls ） { LinkList p, q; q = Ls—>next； if ( q && q-〉next ） { Ls->next = q->next； p=q 62 / 100 while （ p->next ） p = p—>next； p->next = q; q-〉next = NULL； ｝ } 请回答下列问题： (1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。 (2)请简述算法的功能。 31．已知字符串处理函数f31程序如下。 int f31(char＊strl，char*str2） ｛ while(＊strl==*str2&＆（＊strl！=’＼0’）)｛ strl++; str2++； ｝ return（*strl-*str2 ? l∶0)； ｝ 请回答下列问题： （1）若调用语句是f31（”abcde”，”abcdf’），则函数的返回值是什么？若调用语句是 f31（\"abcde\， 则函数的返回值是什么? (2）简述该函数的功能。 32．数组A[]中存储有n个整数，请阅读下列程序。 void f32（intA[],int n) ｛ inti，j，k，x； k=n-l； while（k>0){ i=k； k=0； for（j=O；j 63 / 100 k=j; }／／end of if }／／end of while return; } 请回答下列问题： (1）当A[］={10，8，2，4，6,7}时，执行f32（A，6)后,数组A中存储的结果是什么? （2）说明该算法的功能。 33．下面程序实现二分查找算法。 Typedef struct｛ KeyType key； InfoType otherinfo; }SeqList[N+1］； int BinSearch(SeqList R， int n，KeyType K） { int low=1，high=n； while（ （1） ）{ mid=（1ow+high)／2; if（ （2） ) return mid； if(R[mid]．key>K） high=mid-1； else （3） ； } return O; } ／／BinSearch 请在空白处填写适当内容，使该程序功能完整。 (1） （2） （3) 五、算法设计题（本题10分） 34．已知二叉树采用二叉链表存储，其结点结构定义如下： typedef struct Node{ 64 / 100 ElmType data； struct Node *lchild,＊rchild; }*BiTree； 请编写递归函数SumNodes（BiTree T），返回二叉树T的结点总数。 全国2010年1月高等教育自学考试 数据结构试题及参考答案 课程代码:02331 一、单项选择题(本大题共15小题，每小题2分,共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．若一个算法的时间复杂度用T（n）表示，其中n的含义是（ A ） A．问题规模 C．循环层数 2．具有线性结构的数据结构是( C ） A．树 C．栈和队列 B．图 D．广义表 B．语句条数 D．函数数量 3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为( B ） A．O(1) C．O(n) B．O(m） D．O(m+n） 4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ C ） A．2个 C．4个 B．3个 D．6个 5．假设以数组A［60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素,则队列的尾指针值为（ B ) A．3 C．50 B．37 D．97 6．若栈采用链式存储结构，则下列说法中正确的是（ B ） A．需要判断栈满且需要判断栈空 B．不需要判断栈满但需要判断栈空 C．需要判断栈满但不需要判断栈空 65 / 100 D．不需要判断栈满也不需要判断栈空 7．若串str=”Software”,其子串的数目是（ D ） A．8 C．36 B．9 D．37 8．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 ( C ） A．1012 C．1032 9．允许结点共享的广义表称为( D ) A．纯表 C．递归表 B．线性表 D．再入表 B．1017 D．1039 10．下列数据结构中，不属于二叉树的是（ A ） A．B树 C．二叉排序树 B．AVL树 D．哈夫曼树 11．对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ） ．． A．1,5，2，6，3，4 C．5，1，6，3，4，2 B．1，5,6，2，3，4 D．5，1，2，6，4，3 12．以v1为起始结点对下图进行深度优先遍历,正确的遍历序列是( D ） A．v1，v2，v3，v4，v5，v6，v7 C．v1，v2，v3,v4,v7,v5，v6 B．v1，v2，v5,v4，v3,v7，v6 D．v1，v2,v5，v6，v7,v3，v4 13．下列排序算法中不稳定的是（ A ） A．快速排序 C．冒泡排序 B．归并排序 D．直接插入排序 14．一个有序表为（1，3，9，12，32，41，45，62，75,77,82，95，100），当采用折半查找方法查找值32时,查找 66 / 100 成功需要的比较次数是（ B ） A．2 C．4 B．3 D．8 15．采用ISAM组织文件的方式属于（ D ） A．链组织 C．散列组织 二、填空题(本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上正确答案.错填、不填均无分。 16．数据元素及其关系在计算机存储器内的表示称为__存储结构_______。 17．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是___O( n）______. 18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_________. typedef struct{ DataType data［100]； int top； ｝SeqStack; DataType f18(SeqStack＊S) { if(StackEmpty(S)） Error(”Stack is empty”)； return S-〉data[S->top]； } 19．在串匹配中，一般将主串称为目标串，将子串称为___模式串______. 20．已知广义表C=(a（b，c），d），则:tail(head(tail（C）））= ___（)______。 21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman）树，该树的带权路径长度为 ___221______。 22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是___35______。 B．顺序组织 D．索引组织 23．对序列｛55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是_10,42，12，94，55,01，46，17。 67 / 100 24．高度为3的3阶B-树最少的关键字总数是__13_______. 25．VSAM通常作为大型索引顺序文件的标准组织,其动态索引结构采用的是___B+______. 三、解答题（本大题共4小题，每小题5分，共20分) 26．假设二叉树的RNL遍历算法定义如下： 若二叉树非空，则依次执行如下操作： （1）遍历右子树； （2)访问根节点； （3)遍历左子树。 已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。GCFABDC 27．已知一个无向图G=(V,E)，其中V=｛A，B,C,D，E，F｝，邻接矩阵表示如下所示。 请回答下列问题： (1）请画出对应的图G。 （2)画出图G的邻接表存储结构。 28．已知一组待排记录的关键字序列为(16，12，18,60，15，36，14，18，25,85)，用堆排序方法建小根堆，请给 出初始建堆后的序列。 29．已知一棵二叉排序树如图所示. 请回答下列问题： （1）画出插入元素23后的树结构； (2)请画出在原图中删除元素57后的树结构。 四、算法阅读题(本大题共4小题,每小题5分，共20分） 30．已知下列程序，Ls指向带头结点的单链表. Typedefstruct node { DataType data; 68 / 100 struct node ＊ next； } ＊ LinkList; void f30（ LinkList Ls ） ｛ LinkList p， q； q = Ls->next； if ( q && q—〉next ) { Ls->next = q—〉next； p=q while （ p—〉next ） p = p—〉next; p-〉next = q; q—〉next = NULL; ｝ ｝ 请回答下列问题: (1）当Ls指向的链表如下图所示,请画出执行本函数之后的链表的结果。 （2）请简述算法的功能。 31．已知字符串处理函数f31程序如下。 int f31(char*strl,char＊str2) ｛ while(＊strl==*str2＆&(＊strl!='＼0’))｛ strl++； str2++； ｝ return(＊strl-＊str2 ? l∶0)； } 请回答下列问题： （1）若调用语句是f31(”abcde”,”abcdf’），则函数的返回值是什么?若调用语句是 f31（”abcde”， \"abcde”）,则函数的返回值是什么? (2)简述该函数的功能。 32．数组A［]中存储有n个整数,请阅读下列程序。 void f32（intA［]，int n） { inti，j,k，x； 69 / 100 k=n—l； while（k>0){ i=k； k=0； for(j=O;j 请回答下列问题： (1）当A［]=｛10,8，2，4，6，7}时,执行f32（A,6)后，数组A中存储的结果是什么？ （2）说明该算法的功能. 33．下面程序实现二分查找算法。 Typedef struct｛ KeyType key； InfoType otherinfo； ｝SeqList［N+1]； int BinSearch（SeqList R, int n,KeyType K) ｛ int low=1,high=n; while（ （1) ）｛ mid=（1ow+high）／2; if（ （2) ) return mid； if（R［mid]．key〉K) high=mid-1； else (3） ； ｝ return O; } ／／BinSearch 70 / 100 请在空白处填写适当内容，使该程序功能完整。 (1） （2） (3） 五、算法设计题（本题10分) 34．已知二叉树采用二叉链表存储，其结点结构定义如下： typedef struct Node｛ ElmType data； struct Node *lchild，*rchild; }＊BiTree； 请编写递归函数SumNodes(BiTree T），返回二叉树T的结点总数。 全国2009年10月高等教育自学考试 数据结构试题 课程代码:02331 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．按值可否分解，数据类型通常可分为两类，它们是( ) A．静态类型和动态类型 C．原子类型和结构类型 B．原子类型和表类型 D．数组类型和指针类型 2．对于三个函数f（n)=2008n3+8n2+96000，g（n）=8n3+8n+2008和h（n)=8888nlogn+3n2，下列陈述中不成立的是．（ ) A．f（n)是0(g(n）） C．h（n）是0(nlogn) B．g（n）是0（f（n）) D．h（n）是0(n2） 3．指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点＊q和结点*r在表中次序的程序段是（ ） A．p-〉next=r； q—〉next=r->next； r—>next=q; B．p—〉next=r； r—〉next=q; q—〉next=r—〉next; C．r—〉next=q; q-〉next=r-〉next； p->next=r； D．r—〉next=q; p—>next=r; q—〉next=r-〉next； 71 / 100 4．若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（ ） A．3 C．6 B．5 D．7 5．假设以数组A［n］存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下,队列满的判定条件为（ ） A．rear= =front C．rear+1= =front 6．串的操作函数str定义为： int str(char*s） { char *p=s； while (＊p！=′\\0′)p++； return p-s; } 则str（″abcde″）的返回值是（ ） A．3 C．5 B．4 D．6 B．(front+1）%n= =rear D．（rear+1)％n= =front 7．二维数组A［10］[6］采用行优先的存储方法，若每个元素占4个存储单元,已知元素A［3］［4］的存储地址为1000,则元素A[4］［3］的存储地址为（ ） A．1020 C．1036 B．1024 D．1240 8．对广义表L= （a，(）)执行操作tail(L）的结果是（ ） A．（) C．a B．(()） D．（a） 9．已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（ ） A．FEDCBA C．FDECBA B．ABCDEF D．FBDCEA 10．已知森林F=｛T1，T2，T3，T4，T5｝，各棵树Ti（i=1，2，3,4，5）中所含结点的个数分别为7，3，5，l,2,则与 F对应的二叉树的右子树中的结点个数为（ ） A．2 C．8 B．3 D．11 11．若非连通无向图G含有21条边，则G的顶点个数至少为( ） ．A．7 C．21 B．8 D．22 12．如图所示的有向图的拓扑序列是（ ) 72 / 100 A．c，d，b，a,e B．c,a,d，b，e C．c，d,e,a,b D．c，a，b，d，e 13．对关键字序列（6，1，4，3，7，2，8，5）进行快速排序时,以第1个元素为基准的一次划分的结果为( ） A．(5，1，4,3，6，2,8，7） C．(5,1，4，3，2,6，8,7) B．（5，1，4，3，2，6，7，8） D．（8,7，6，5,4,3,2，1) 14．分块查找方法将表分为多块,并要求（ ） A．块内有序 C．各块等长 B．块间有序 D．链式存储 15．便于进行布尔查询的文件组织方式是（ ) A．顺序文件 C．散列文件 二、填空题（本大题共10小题，每小题2分，若有两个空格,每个空格1分,共20分） 请在每个空格中填上正确答案。错填、不填均无分. 16．数据的链式存储结构的特点是借助________表示数据元素之间的逻辑关系。 17．如果需要对线性表频繁进行________或________操作，则不宜采用顺序存储结构. 18．如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是top1=0，栈2为空的条 件是top2=n-1，则“栈满”的判定条件是________。 19．静态存储分配的顺序串在进行插入、置换和________等操作时可能发生越界。 20．广义表L=（a，（b，（ )））的深度为________。 21．任意一棵完全二叉树中,度为1的结点数最多为________。 22．求最小生成树的克鲁斯卡尔（Kruskal）算法耗用的时间与图中________的数目正相关. 23．在5阶B—树中，每个结点至多含4个关键字，除根结点之外，其他结点至少含________个关键字。 24．若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是________的。 25．常用的索引顺序文件是________文件和________文件。 三、解答题（本大题共4小题,每小题5分，共20分) 26．如图所示，在n×n矩阵A中,所有下标值满足关系式i+j＜n+l的元素aij的值均为0，现将A中其它元素按行优 先顺序依次存储到长度为n(n+1）/2的一维数组sa中，其中元素a1,n存储在sa［0］。 （1）设n=10，元素a4，9存储在sa［p］,写出下标p的值； (2)设元素ai，j存储在sa[k］中，写出由i，j和n计算k的一般公式。 73 / 100 B．索引文件 D．多关键字文件 27．由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如图所示.已知某段电文的哈夫曼编码为 111000010100，请根据该哈夫曼树进行译码，写出原来的电文。 28．已知无向图G的邻接表如图所示, （1）画出该无向图； （2）画出该图的广度优先生成森林. 29．对序列(48,37,63,96，22,31，50，55，11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序 列状态。 初始堆: 第1趟： 74 / 100 第2趟： 四、算法阅读题（本大题共4小题，每小题5分,共20分) 30．阅读下列算法，并回答问题： （1)无向图G如图所示，写出算法 f30(&G)的返回值； (2）简述算法f30的功能. #define MaxNum 20 int visited[MaxNum］； void DFS(Graph *g，int i）； /*从顶点vi出发进行深度优先搜索，访问顶点vj时置visited［j]为1*/ int f30（Graph *g) { int i，k; for (i=0； i visited[i]=0； for （i=k=0； i 31．假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下: typedef struct Node ｛ int id; /*学号＊/ int score； /＊成绩*/ struct Node ＊next; ｝ LNode， *LinkList； 阅读算法f31，并回答问题： （1)设结点结构为 f31（A，B)后A所指的链表; ，成绩链表A和B如图所示，画出执行算法 75 / 100 (2）简述算法f31的功能。 void f31（LinkList A, LinkList B） { LinkList p， q; p=A—>next； q=B—〉next； while （p ＆＆ q) ｛ if (p—>id〈q—>id） p=p-〉next； else if （p—〉id〉q—>id） q=q-〉next； else { if (p—>score<60) if (q->score<60） p—>score=q->score; else p-〉score=60; p=p—>next； q=q—〉next; ｝ } ｝ 32．阅读下列算法，并回答问题： （1）设串s=“OneWorldOneDream\"，t=＂One＂，pos是一维整型数组,写出算法 f32(s，t,pos)执行之后得到的返回值和pos中的值； （2）简述算法f32的功能。 int strlen（char＊s）; /*返回串s的长度*/ int index(char＊st，char＊t)； ／＊若串t在串st中出现,则返回在串st中首次出现的下标值，否则返回-1*/ int f32(char＊s， char＊t, int pos[］） { int i， j, k, ls, lt; ls=strlen（s); 1t=strlen（t)； 76 / 100 if (ls= =0｜｜1t= =0） return-1； k=0； i=0; do ｛ j=index（s+i， t）; if （j〉=0) ｛ pos[k++]=i+j； i+=j+1t; ｝ }while(i+1t〈=1s ＆& j 〉=0）； return k； ｝ 33．二叉排序树的存储结构定义为以下类型: typedef int KeyType； typedef struct node ｛ KeyType key； /*关键字项＊/ InfoType otherinfo; /＊其它数据项*/ struct node *1child, *rchild; /*左、右孩子指针＊/ } BSTNode, *BSTree; 阅读算法f33，并回答问题： （1)对如图所示的二叉排序树T，写出f33(T，8） 返回的指针所指结点的关键字； （2)在哪些情况下算法f33返回空指针？ (3）简述算法f33的功能。 BSTNode ＊f33(BSTree T， KeyType x) { BSTNode *p； if （T= =NULL） return NULL； p=f33（T-〉1child, x); if (p!=NULL）return p; if （T-〉key>x)return T； return f33（T—〉 rchild, x）; ｝ 五、算法设计题（本题10分） 77 / 100 34．假设线性表采用顺序存储结构，其类型定义如下： #define ListSize 100 typedef struct { int data［ListSize］; int length; } SeqList, ＊Table； 编写算法,将顺序表L中所有值为奇数的元素调整到表的前端。 2009年10月 数据结构 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内.错选、多选或未选均无分。 1．按值可否分解，数据类型通常可分为两类,它们是（ C ) A．静态类型和动态类型 B．原子类型和表类型 C．原子类型和结构类型 D．数组类型和指针类型 3232 2．对于三个函数f（n)=2008n+8n+96000，g(n)=8n+8n+2008和h(n）=8888nlogn+3n,下列陈述中不成立的是（ C ） ．A．f(n）是0(g(n)) B．g（n）是0（f（n）) C．h（n)是0（nlogn） D．h（n)是0(n) 3．指针p、q和r依次指向某循环链表中三个相邻的结点,交换结点*q和结点*r在表中次序的程序段是( A ） A．p—>next=r； q—〉next=r—〉next； r—>next=q; B．p-〉next=r； r—>next=q； q—>next=r—〉next； C．r->next=q； q->next=r—〉next； p->next=r; D．r->next=q; p—>next=r; q—〉next=r—>next； 4．若进栈次序为a，b，c,且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（ B ） 2 78 / 100 A．3 B．5 C．6 D．7 5．假设以数组A［n]存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为（ D ） A．rear= =front B．(front+1)%n= =rear C．rear+1= =front D．（rear+1)％n= =front 6．串的操作函数str定义为: int str(char*s） ｛ char ＊p=s; while (＊p！=′\\0′）p++； return p-s； ｝ 则str（″abcde″）的返回值是（ C ） A．3 B．4 C．5 D．6 7．二维数组A［10]［6］采用行优先的存储方法,若每个元素占4个存储单元，已知元素A［3][4］的存储地址为1000，则元素A[4］［3］的存储地址为（ A ) A．1020 B．1024 C．1036 D．1240 8．对广义表L= （a,(））执行操作tail(L）的结果是（ B ） A．（） B．（(）） C．a D．（a) 9．已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（ A ） A．FEDCBA B．ABCDEF C．FDECBA D．FBDCEA 10．已知森林F={T1,T2,T3，T4，T5｝,各棵树Ti（i=1,2,3，4,5）中所含结点的个数分别为7,3,5，l，2，则与F对 应的二叉树的右子树中的结点个数为( D ） A．2 B．3 C．8 D．11 11．若非连通无向图G含有21条边，则G的顶点个数至少为（ B ） ．A．7 B．8 C．21 D．22 12．如图所示的有向图的拓扑序列是（ B ） A．c，d,b,a，e B．c，a，d，b,e C．c，d,e,a，b D．c,a,b，d,e 13．对关键字序列（6,1,4,3，7，2,8,5）进行快速排序时，以第1个元素为基准的一次划分的结果为（ C ） A．（5,1,4,3,6,2，8，7） B．(5，1,4，3,2，6，7，8） C．（5,1,4，3,2，6，8，7） D．（8,7,6，5,4，3，2,1） 14．分块查找方法将表分为多块,并要求（ B ） A．块内有序 B．块间有序 C．各块等长 D．链式存储 15．便于进行布尔查询的文件组织方式是（ D ） A．顺序文件 B．索引文件 C．散列文件 D．多关键字文件 二、填空题(本大题共10小题,每小题2分，若有两个空格，每个空格1分,共20分） 请在每个空格中填上正确答案。错填、不填均无分。 16．数据的链式存储结构的特点是借助 指针 表示数据元素之间的逻辑关系。 17．如果需要对线性表频繁进行 插入 或 删除 操作，则不宜采用顺序存储结构。 18．如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是top1=0，栈2为空的 条件是top2=n—1,则“栈满”的判定条件是 top1〉top2（或top2=top1-1或top1=top2+1) 。 19．静态存储分配的顺序串在进行插入、置换和 联接 等操作时可能发生越界。 20．广义表L=（a，（b，( )））的深度为 3 。 21．任意一棵完全二叉树中，度为1的结点数最多为 1 。 79 / 100 22．求最小生成树的克鲁斯卡尔（Kruskal)算法耗用的时间与图中 边 的数目正相关。 23．在5阶B—树中,每个结点至多含4个关键字,除根结点之外，其他结点至少含 2 个关键字。 24．若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 稳定 的。 25．常用的索引顺序文件是 ISAM 文件和 VSAM 文件. 三、解答题(本大题共4小题，每小题5分，共20分) 26．如图所示，在n×n矩阵A中,所有下标值满足关系式i+j＜n+l的元素aij的值均为 0,现将A中其它元素按行优先顺序依次存储到长度为n(n+1)/2的一维数组sa中，其中元素a1，n存储在sa［0]. （1)设n=10,元素a4，9存储在sa［p］,写出下标p的值； (2)设元素ai，j存储在sa［k］中，写出由i，j和n计算k的一般公式. 27．由字符集｛s，t，a,e,I}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某 段电文的哈夫曼编码为111000010100,请根据该哈夫曼树进行译码，写出原来的电文。答案：eatst 28．已知无向图G的邻接表如图所示, (1）画出该无向图； (2)画出该图的广度优先生成森林。 29．对序列(48,37，63，96，22,31，50，55，11）进行升序的堆排序，写出构建的初始（大根)堆及前两趟重建 堆之后的序列状态。 初始堆： 第1趟: 第2趟： 四、算法阅读题（本大题共4小题,每小题5分，共20分) 30．阅读下列算法，并回答问题： (1）无向图G如图所示,写出算法f30（＆G）的返回值; 3 (2）简述算法f30的功能。返回无向图g中连通分量的个数. ＃define MaxNum 20 int visited［MaxNum]； void DFS(Graph *g，int i)； /*从顶点vi出发进行深度优先搜索,访问顶点vj时置visited［j]为1*/ int f30（Graph *g) ｛ int i，k； for （i=0； i〈g-〉n; i++)／＊g—〉n为图g的顶点数目＊／ visited［i］=0； for （i=k=0； i if （visited[i]= =0) ｛ k++; DFS(g,i）； ｝ 80 / 100 return k； } 31．假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node { int id； /*学号*/ int score； /＊成绩*/ struct Node ＊next； } LNode， *LinkList； 阅读算法f31,并回答问题： （1）设结点结构为 ，成绩链表A和B如图所示,画出执行算法 f31（A,B）后A所指的链表； （2）简述算法f31的功能。 void f31(LinkList A, LinkList B) ｛ LinkList p， q; p=A-〉next; q=B—〉next; while (p ＆& q) { if (p—>id〈q—>id） p=p—>next; else if （p—〉id>q-〉id） q=q-〉next; else { if (p—〉score<60） if （q-〉score<60) p—〉score=q-〉score; else p-〉score=60； p=p—>next； q=q—>next； ｝ } ｝ 32．阅读下列算法，并回答问题: （1)设串s=“OneWorldOneDream”,t=＂One＂,pos是一维整型数组,写出算法 f32(s，t,pos）执行之后得到的返回值和pos中的值； （2)简述算法f32的功能。 int strlen（char＊s); /＊返回串s的长度*/ int index(char*st，char*t）； ／*若串t在串st中出现，则返回在串st中首次出现的下标值，否则返回-1＊/ int f32(char*s, char*t, int pos［］) ｛ int i, j, k， ls, lt； 81 / 100 ls=strlen（s）； 1t=strlen（t）； if (ls= =0｜｜1t= =0） return—1; k=0； i=0; do { j=index（s+i, t); if (j〉=0) { pos[k++]=i+j； i+=j+1t; ｝ ｝while(i+1t〈=1s ＆＆ j 〉=0）； return k; } 33．二叉排序树的存储结构定义为以下类型： typedef int KeyType； typedef struct node { KeyType key; /*关键字项＊/ InfoType otherinfo； /＊其它数据项＊/ struct node ＊1child， ＊rchild; /*左、右孩子指针＊/ } BSTNode, *BSTree； 阅读算法f33，并回答问题： （1)对如图所示的二叉排序树T,写出f33（T,8） 返回的指针所指结点的关键字； （2）在哪些情况下算法f33返回空指针? （3）简述算法f33的功能。 BSTNode *f33(BSTree T, KeyType x) ｛ BSTNode ＊p； if (T= =NULL) return NULL； p=f33（T-〉1child， x）; if （p!=NULL)return p； if （T—〉key〉x)return T； return f33(T-> rchild， x）； } 五、算法设计题（本题10分) 34．假设线性表采用顺序存储结构,其类型定义如下： ＃define ListSize 100 typedef struct { int data［ListSize]； int length; 82 / 100 } SeqList, ＊Table; 编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。 2007年1月高等教育自学考试全国统一命题考试 数据结构试题 课程代码2331 83 / 100 一、单项选择题（本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．抽象数据类型的三个组成部分分别为( ） A．数据对象、数据关系和基本操作 B．数据元素、逻辑结构和存储结构 C．数据项、数据元素和数据类型 D．数据元素、数据结构和数据类型 2．若算法中语句的最大频度为T(n)=2006n+6nlogn+29log2n,则其时间复杂度为（ ) A．O(logn） C．O(nlogn） B．O(n) D．O(log2n) 3．若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为 （ ） A．无头结点的双向链表 C．无头结点的单链表 4．上溢现象通常出现在（ ） A．顺序栈的入栈操作过程中 C．链栈的入栈操作过程中 B．顺序栈的出栈操作过程中 D．链栈的出栈操作过程中 B．带尾指针的循环链表 D．带头指针的循环链表 5．已知串s=″aabacbabcaccab″,串t1=″abc″，串t2=″cba″，函数index(s，t)的返回值为串t在串s中首次出现的位置，则能求得串″abcacba″的操作序列为（ ） A．substr （s1,s,6，index(s,t1)）； substr (s2,s，index(s，t1）,1)；strcat（s1，s2)； B．substr (s1，s，7，index（s，t1）)； substr （s2,s,index（s，t1）,1）；strcat(s2,s1); C．substr(s1，s,6,index（s,t2)）； substr（s2,s,index(s，t2),3)；strcat(s1,s2）; D．substr(s1,s,6，index(s,t2））； substr(s2，s，index（s，t2),3）;strcat（s2，s1)； 6．对广义表L=（(a,b），((c,d）,(e，f)））执行head(tail(head(tail（L）)））操作的结果是( ) A．d C．（e） B．e D．(e,f ） 7．已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为( ) A．7 C．9 B．8 D．10 8．若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是( ) A．10 C．12 B．11 D．不确定的 9．对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为( ） 84 / 100 A．求一个顶点的邻接点 C．深度优先遍历 B．求一个顶点的度 D．广度优先遍历 10．若用邻接矩阵表示带权有向图，则顶点i的入度等于矩阵中（ ) A．第i行非∞元素之和 C．第i行非∞元素个数 B．第i列非∞元素之和 D．第i列非∞元素个数 11．对关键字序列（5，1，4，3,7，2，8，6)进行快速排序时，以第一个元素5为基准的一次划分的结果为（ ） A．（1，2，3，4，5，6，7，8） C．（2，1，4，3，5,7，8，6） B．（1,4，3,2,5，7，8，6） D．（8，7，6，5，4，3,2，1） 12．下列二叉树中，不平衡的二叉树是( ） ． 13．下列序列中，不构成堆的是（ ） ．A．(1,2，5，3，4,6，7，8,9，10） B．（10，5，8，4，2，6,7，1,3） C．（10，9，8,7，3，5，4，6,2) D．(1,2，3，4，10，9，8，7,6，5） 14．主关键字能唯一标识（ ） A．一个记录 C．一个类型 B．一组记录 D．一个文件 15．稀疏索引是指在文件的索引表中（ ) A．为每个字段设一个索引项 C．为每组字段设一个索引项 B．为每个记录设一个索引项 D．为每组记录设一个索引项 二、填空题(本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．链式存储结构的特点是借助_______来表示数据元素之间的逻辑关系。 17．假设带头结点的非空单循环链表中仅设尾指针L，则在第1个结点之前插入指针s所指结点的语句依次是_______；_______。 18．无表头结点的链队列Q为空的条件是_______。 19．不含任何字符的串称为_______。 ． 85 / 100 20．假设按行优先顺序将一个20阶的三对角矩阵A压缩存储在一维数组Q中，其中Q[0]存放矩阵的第1个元素a1,1，那么矩阵元素a3,4在Q中的存储位置k=_______. 21．前序序列和中序序列不相同的二叉树的特征是_______. ． 22．在含有n个顶点的连通图中，任意两个不同顶点之间的简单路径的最大长度为_______. 23．用_______排序方法对关键字序列(20，25，12，47，15，83，30，76）进行排序时，前三趟排序的结果为： 20，12，25，15，47，30，76，83 12,20,15，25，30,47，76,83 12，15，20，25,30，47，76，83 24．哈希表常用的两类解决冲突的方法是_______和_______。 25．倒排文件和多重表文件的主要区别在于_______的结构不同。 三、解答题（本大题共4小题，每小题5分,共20分) 26．已知主串为″ccgcgccgcgcbcb″，模式串为″cgcgcb″。下表所列为按照朴素的串匹配算法进行的前两趟匹配。请继续完成余下各趟匹配，直至结束。 86 / 100 27．已知带权图G如图所示,画出图G的一棵最小生成树. 28．对于直接插入排序，希尔排序,冒泡排序，快速排序,直接选择排序,堆排序和归并排序等排序方法,分别写出： (1）平均时间复杂度低于O（n2）的排序方法; （2）所需辅助空间最多的排序方法； （3）最好情况和最坏情况下的时间复杂度相同的排序方法. （1） （2） （3） 87 / 100 29．已知一棵线索化的二叉排序树如图所示。 （1）说明该树的线索化是基于何种遍历次序的; （2）在该树中插入元素值为53的结点并修改相应线索，画出修改之后的树. （1） (2） 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f 30，并回答下列问题： （1)设顺序表L=（3，7，3，2,1,1,8,7,3)，写出执行算法f 30后的L; （2）简述算法f 30的功能. void f 30（SeqList ＊L) { int i，j,k; k=0; for（i=0;i ｛ for(j=0;j L—〉length=k; ｝ （1) (2) 31．阅读算法f 31，并回答下列问题： (1）设队列Q=（1，3，5，2，4，6）。写出执行算法f 31后的队列Q; （2）简述算法f 31的功能。 void f 31（Queue *Q）{ 88 / 100 DataType e; if （!QueueEmpty（Q）)｛ e=DeQueue（Q)； f 31(Q)； EnQueue（Q，e)； } ｝ （1） （2) 32．已知树的存储结构为孩子兄弟链表，其类型定义如下： typedef struct CSTNode ｛ char data； struct CSTNode leftmostchild，*rightsibling； } CSTNode， *CSTree; 阅读函数f 32，并回答下列问题： （1）对于如图所示树，写出函数调用f 32（T）的返回值； （2)简述树T非空时函数f 32返回值的含义。 int f32(CSTree T）{ int c； CSTree p; if （！T->leftmostchild) return 1； else ｛ c=0； for（p=T-〉leftmostchild；p;p=p->rightsibling) c+=f32（p)； return c； ｝ } （1） （2） 33．已知数组R［1..p-1］中的元素序列为一个大根堆，函数Adjust(R，p)将R[1。.p］重新调整为一个大根堆。 （1)在函数Adjust的空缺处填入适当内容，使其成为一个完整的函数; （2）简述函数f33（R,n）的功能。 void Adjust（SeqList R，int p) 89 / 100 ｛ int i，j; RecType temp=R[p]； i=p; j=i/2; while（j〉=1＆& R［j].key〈temp。key) ｛ R[i］=R［j]； i=j； ① ; ｝ R[i]= ② ; } void f33(SeqList R,int n) { int k； for(k=2;k〈=n；k++) Adjust(R,k）； ｝ （1）① ② (2） 五、算法设计题(本大题10分） 34．已知有向图的邻接表表示的形式描述如下： ＃define MaxNum 50 //图的最大顶点数 typedef struct ArcNode { int adjvex； //邻接点域 struct ArcNode ＊nextArc; //链域 } ArcNode； //弧结点类型 typedef struct { char vertex; //顶点域 ArcNode ＊firstArc； //弧表头指针 ｝VertexNode; //顶点表结点类型 typedef struct ｛ VertexNode adjList［MaxNum]； //邻接表 90 / 100 int n，e; //图中当前的顶点数和边数 ｝ALGraph; //邻接表类型 按以下函数原型编写算法，求有向图G中第i顶点的度,并写出算法的时间复杂度。 int f34(ALGraph *G,int i）; 91 / 100 92 / 100 93 / 100 94 / 100 绝密★考试结束前 全国2013年1月高等教育自学考试 数据结构试题 课程代码：02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1．答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2．每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑.如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 纸”的相应代码涂黑.错涂、多涂或未涂均无分. 1．数据的逻辑结构可以分为 A．动态结构和静态结构 C．线性结构和非线性结构 B.顺序结构和链式结构 D.简单结构和构造结构 2．线性表是一个有限序列，组成线性表的基本单位是 A．数据项 C．数据域 能的出栈序列是 ．A．dcba C．cadb 4．稀疏矩阵的三元组表是 A．顺序存储结构 C．索引存储结构 B。链式存储结构 D.散列表存储结构 B。cbda D.cdba B。数据元素 D。字符 3．栈中有a、b和c三个元素,a是栈底元素，c是栈顶元素，元素d等待进栈，则不可 ．． 5．已知广义表G,head（G）与tail(G）的深度均为6，则G的深度是 A．5 C．7 6．下列编码集合中，属于前缀编码的一组是 95 / 100 B.6 D。8 A。｛11,10,001,101,0001} C。{11，01,001，0101,0001} 7.如题7图所示二叉树的中序序列为 A．ACDB B．DCBA C．CDBA D．ABCD B.｛00,010,0110，1000｝ D.｛0,10，110，1011} 题7图 8．有向图中所有顶点入度之和与所有顶点出度之和的比是 A．1/2 C．2 B.1 D。4 9．含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是 A。e C。n2-2e 10.n个顶点的无向连通图,其生成树的边数为 A.n-l C。n+l B.n D。nlogn B。2e D。n2-e 11．用自底向上的冒泡排序方法对序列(8，13，26，55,29，44)从大到小排序，第一趟排序需进行交换的次数为 A．2 C．4 B.3 D.5 12．对序列(8,13，26，55,29，44）从小到大进行基数排序，第一趟排序的结果是 A。（13,44，55,26，8，29) C。（8,13,26，29，44,55） 13．采用分块查找时，要求数据 A．块内有序 C．分块无序 14。下列关于散列函数的说法正确的是 A．散列函数越复杂越好 B。散列函数越简单越好 C．用除余法构造的散列函数是最好的 D.在冲突尽可能少的情况下，散列函数越简单越好 15。下列关于m阶B树的叙述中，错误的是 ．．A．每个结点至多有m棵子树 B。每个结点至多有m-1个关键字 96 / 100 B.（13，26，55，44,8,29) D。（29，26，8,44,55,13) B.分块有序 D.每块中数据个数必须相同 C．所有的叶结点均在同一层上 D.根结点至少有m/2棵子树 非选择题部分 注意事项: 用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上. 二、填空题(本大题共10小题，每小题2分，共20分） 16．算法的时间复杂度与实现时采用的程序设计语言____________。 17．在长度为n的顺序表的第i(1≤i≤n)个元素之后插入一个元素时，需向后移动___________个元素。 18．设循环队列存放在向量data［0。.m-l］中,在出队操作后，队头指针front变化为___________。 19．树的前序遍历序列等同于该树对应二叉树的____遍历序列. 20．一个100×90的整型稀疏矩阵有10个非零元素，设每个整型数占2个字节,则用三元组表存储该矩阵时，所需的字节数是___________. 21．当用二叉链表作为n个结点的二叉树的存储结构时，空指针域的个数是____。 22．采用邻接表表示n个顶点的有向图时，若表结点的个数为m，则该有向图的边数 为___________。 23．对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的 算法是___________。 24．在16个记录的有序顺序表中进行二分查找，最大比较次数是___________。 25．在排序算法中，若排序前后具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是___________的. 三、解答题（本大题共4小题，每小题5分,共20分) 26．在定义顺序表时，存放表结点的向量空间不宜过大也不宜过小，为什么？ 27．画出题27图所示树的孩子链表. 题27图 28．已知一个无向图G如题28图所示，以顶点①为根，且小序号优先,分别画出G的深度优先生成树和广度优先生成树。 97 / 100 题28图 29．判别以下序列是否为堆，若不是，将其调整为大根堆，并画出大根堆。 ①(1，5，7，20，18，8,10，40） ②(18,9，5，8，4,17,21，6) 四、算法阅读题（本大题共4小题,每小题5分，共20分) 30．单链表类型定义如下： typedef struct node { DataType data； struct node ＊next; ｝ListNode； typedef ListNode ＊LinkList; 阅读下列算法,并回答问题: void f30 （LinklList head, DataType x) { ∥head是带头结点的非空单链表的头指针 ListNode ＊p， ＊q; p=head； while（p-〉next-〉next） p=p-〉next； q=(ListNode＊) malloc （sizeof（ListNode)）； q—〉data=x； q-〉next=p—>next； p—>next=q； } (1）该算法的功能是什么? (2)若单链表的长度为n,算法的时间复杂度是多少？该时间复杂度和链表的初始状态有关吗? 31．阅读下列算法(假设栈的操作函数都已定义），并回答问题： void f31 （ ) { SeqStack S； 98 / 100 char x， y； x=′c′； y=′k′； Push （＆S，x）; Push (＆S,′a′)； Push （＆S，y)； x=Pop（＆S）； Push（＆S,′t′)； Push（＆S,x)； x=Pop（＆S)； Push（&S，′s′）； while ( !StackEmpty(＆S)) ｛ y=Pop (＆S）； putchar （y); } putchar (x)； ｝ （1）自底向上写出执行while语句之前栈S中的元素序列. （2）写出该函数的最后输出结果。 32．下列算法的功能是在中序线索树中查找结点*p的前趋，填上适当内容使算法完整。 typedef enum ｛ Link,Thread ｝ PointerTag； ∥ 枚举值Link和Thread分别为0和1 typedef struct node ｛ DataType data; PointerTag ltag， rtag； Struct node *lchild, ＊rchild； ｝BinThrNode； BinThrNode＊f32 （BinThrNode ＊p) { ∥ 在中序线索树中找结点*p的中序前趋，设p非空 BinThrNode ＊q; if（p—>ltag==Thread) (1) ; else ｛ q=p—〉lchild； 99 / 100 while（q-〉rtag=Link) （2） ; return q； ｝ ｝ 33．分析下列排序算法中语句1和语句2的频度以及此算法的时间复杂度，并指出该算法是属于哪一种排序方法。 void f33( int a[ ]，int n ） { int i，j,k,t； for (i=0;i if (a[k］ typedef struct node ｛ int data； struct node *lchild,＊rchild; ｝*BSTree； 编写递归算法从小到大输出二叉排序树T中所有data域值大于m且小于n的数据。 函数原型为void f34（BSTree T， int m， int n） 100 / 100 因篇幅问题不能全部显示，请点此查看更多更全内容