 上传我的文档
 下载
 收藏
粉丝量：22
该文档贡献者很忙，什么也没留下。
 下载此文档
算法分析试题
下载积分：400
内容提示：算法分析试题
文档格式：DOC|
浏览次数：129|
上传日期： 22:10:13|
文档星级：
全文阅读已结束，如果下载本文需要使用
 400 积分
下载此文档
该用户还上传了这些文档
算法分析试题
关注微信公众号当前位置： >>
2012年10月--2007年1月自考2331数据结构历年试题和答案
全国 2012 年 10 月高等教育自学考试数据结构试题课程代码：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==NULL4．设以数组 A[0..m-1]存放循环队列，front 指向队头元素，rear 指向队尾元素的下一个位 置，则当前队列中的元素个数为 A．(rear-front+m)％m C．(front-rear+m)％m B．rear-front+1 D．(rear-front)％m1 / 1005．下列关于顺序栈的叙述中，正确的是 A．入栈操作需要判断栈满，出栈操作需要判断栈空 B．入栈操作不需要判断栈满，出栈操作需要判断栈空 C．入栈操作需要判断栈满，出栈操作不需要判断栈空 D．入栈操作不需要判断栈满，出栈操作不需要判断栈空 6．A 是一个 10× 的对称矩阵，若采用行优先的下三角压缩存储，第一个元素 a0,0 的存储 10 地址为 1，每个元素占一个存储单元，则 a7,5 的地址为 A．25 C．33 7．树的后序遍历等价于该树对应二叉树的 A．层次遍历 C．中序遍历 8．使用二叉线索树的目的是便于 A．二叉树中结点的插入与删除 C．确定二叉树的高度 B．在二叉树中查找双亲 D．查找一个结点的前趋和后继 B．前序遍历 D．后序遍历 B．26 D．349．设无向图的顶点个数为 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．n213．对线性表进行二分查找时，要求线性表必须是 A．顺序存储 B．链式存储2 / 100C．顺序存储且按关键字有序D．链式存储且按关键字有序14．分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同 ．． 的序列是 A．(4,1,2,3,5) C．(4,5,2,1,3) 15．下列关于 m 阶 B 树的叙述中，错误的是 ．． A．每个结点至多有 m 个关键字 B．每个结点至多有 m 棵子树 C．插入关键字时，通过结点分裂使树高增加 D．删除关键字时通过结点合并使树高降低 B．(4,2,3,l,5) D．(4,2,1,5,3)非选择题部分注意事项： 用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。二、填空题(本大题共 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 出队； g,h,i,j,k,l 入队，e,f,g,h 出队； M,n,o,P 入队， (1) Q.front=______；Q.rear=______。 (2) Q.front=______；Q.rear=______。 (3) Q.front=______；Q.rear=______。i,j,k,l,m 出队；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 { int i,j； i=0； while(i&L-&length) if (L-&data[i]％2!=0) { for(j=i+1; j&L-& 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 ET typedef struct{ EType edges[MVN][MVN]; ∥ 邻接矩阵，即边表 ｝MG ∥ 图的顶点数 ∥ 图类型 ∥ 最大顶点数 ∥ 边上权值类型 *L)例如，一个有向图的邻接矩阵如下所示：?0 ?1 ? A ? ?0 ? ?1 ?0 ? 1 0 0 0? 0 0 0 1? ? 1 0 1 0? ? 0 0 0 0? 0 0 1 1? ?阅读下列算法，并回答问题：5 / 100Void f31(MGraph { Int i,j,k=0; Step1:G)for (i=0; i&G.n; i++) for (j=0; j&G.n; j++) if (G.edges[i][j]= =1) k++; printf(“%d step2: for (j=0; j&G.n; j++) { k=0; n”,k);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&n；i++) { r[0]=r[i]； j=i-l； while (r[0]&r[j]) { r[j+l]=r[j]； j=j-1； }6 / 100n”,k);r[j+l]=r[0]； } } (1)这是哪一种插入排序算法?该算法是否稳定? (2)设置 r[0]的作用是什么? 33．顺序表类型定义如下： typedef int SeqList[100]； 阅读下列算法，并回答问题： void f33(SeqList r， { 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 } BinNode； typedef BinNode* *int n)}n＂，a，b)；lchild，*rchild；BinTree；编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的和。7 / 100函数的原型为：void f34(BinTree T, int**count, int*sum)count 和*sum 的初值为 0。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.串的长度必须大于零 B.n-i D.不确定5.无向完全图 G 有 n 个结点，则它的边的总数为11 / 100A.n2 C.n(n-1)/2B.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.数据分成若干块，每块内数据不必有序，但块间必须有序 13.下述编码中不是前缀码的是12 / 100B.快速 D.冒泡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-115.在一个以 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)简述该算法的功能； (2)写出分别输入字符串：&abcba&和&abcbde&，调用算法函数的返回值。14 / 100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;j&i/2.j++) push(&s,str[j])； if (i％2!=0) k=i/2+1； else k=i／2； for (j=k;j&i;j++) if (str[j]!=pop(&s)) return 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; while (low&=high)15 / 100{mid=(low+high)/2； if (x.key&R[mid].key) else (2) ； (1) ；} 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; 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))； scanf(&％c&，&ch)；16 / 100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&MaxLen-1 int k，i； 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].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－＞p2－＞next=p1－＞ B. p2－＞next=p1－＞p1－＞next=p2－＞ C. p=p2－＞ p1－＞next=p;p2－＞next=p1－＞ D. p=p1－＞ 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.队列的特点是（ ） ） B.3 个 D.6 个A.允许在表的任何位置进行插入和删除 B.只允许在表的一端进行插入和删除 C.允许在表的两端进行插入和删除 D.只允许在表的一端进行插入，在另一端进行删除 6.一个链串的结点类型定义为 |define NodeSize 621 / 100typedef struct node{ char data[NodeSize]; struct node* }LinkStrN 如果每个字符占 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.2D.无限值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-112.要以 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 开始）? 0 ? 0 ? ? ?8 ? ? 0 ? 0 ?007 ?1 0 5 0 0 0 60 0? 0 0? ? 0 0? ? 0 0? ?2 9 ? ?（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 1 B 2 C 3 D 4 E 5 F 6 G 7画出执行函数 f32（BT,7,1）的返回结果; (2)简述函数 f32 的功能。 BinTree f32(DataType {25 / 100BT[],int n,int i)BinT 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 } (1) (2) 33.已知有向图的邻接表和邻接矩阵定义如下： |define MaxNum 50 typedef struct node { struct node * } EdgeN struct{ ∥顶点域 ∥边表头指针 ∥顶点表结点结构 ∥邻接点域 ∥链指针域 ∥边表结点结构 ∥图的最大顶点数typedefchar vertex； EdgeNode * } VertexN struct { adjlist [MaxNum];typedefVertexNode int n,e; } ALG typedef struct{ char int int∥邻接表 ∥图中当前顶点数和边数 ∥邻接表描述的图vertex[MaxNum]; adjmatrix [MaxNum][MaxNum]; n,e;∥顶点表 ∥邻接矩阵 ∥图中当前顶点数和边数 ∥邻接矩阵描述的图26 / 100} AMG下列算法是将邻接表描述的图 G1 改为邻接矩阵描述的图 G2， 在空白处填上适当内容使算 法完整： void { int f33（ALGraph G1,AMGraph *G2） i, *p;EdgeNodeG2－＞n=G1.n; G2－＞e= for { (1) ;(i=0; i＜G1.n; i++) G2－＞vertex[i]= (2) ;p=G1.adjlist[i]. for while { (j=0; (p) G2－＞adjmatrix[i][p－＞adjvex]=1; (3) } } } (1) (2) (3) 五、算法设计题（本题 10 分） 34.设顺序表Ｌ是一个递增有序表。编写算法，要求利用二分查找法确定插入位置，将元素 ｘ插入到Ｌ中，使Ｌ保持有序。 ; j＜G1.n; j++） G2－＞adjmatrix[i][j]=0;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.2n3.已知循环队列的存储空间大小为 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.下列叙述中错误的是（ ） ） B.5 D.8A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次 B.图的遍历可以采用深度优先遍历和广度优先遍历 C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程 10.已知有向图 G=(V，E)，其中 V={V1，V2，V3，V4}，E={&V1，V2&，&V1，V3&，&V2， V3&，&V2，V4&，&V3，V4&}，图 G 的拓扑序列是（ A.V1,V2,V3,V4 C.V1,V3,V4,V2 B.V1,V3,V2,V4 D.V1,V2,V4,V3 ） ）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 ? (1)已知矩阵 B= ? 4 ?7 ? 2 5 8 3? ? 6 ? ，将其按行优先存于一维数组 A 中，给出执行函数调 9? ?用 f30(A，3)后矩阵 B 的值； (2)简述函数 f30 的功能。 31.假设以二叉链表表示二叉树，其类型定义如下： typedef struct node {35 / 100struct node*Ichild, * } *BinTree；∥左右孩子指针阅读下列程序。 void f31(BinTree T) { InitStack(S); ∥ 初始化一个堆栈 S while (T { while { Push(S,T); } if (!StackEmpty(S)) { T=Pop(S); printf(“%c”,T-&data); T=T-& } } } 回答下列问题： (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&n； j++)36 / 100||!StackEmpty(S)(T)T=T-&printf(“%d ”,A[j])； printf(“＼n”); m=0： for (j=1; j&n-i; j++) if (A[j-1]&A[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 KeyT typedef struct { KeyT InfoT } NodeType； typedef NodeType 阅读下列程序。 Int f33(SqList R，NodeType X, { if (p&q) return -1; int p, int q) SqList[MAXLEN];m=(p+q)／2； if (R[m].key==X.key)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 { struct node* }LinkNode，*LinkL 编写程序，求头指针为 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!=head4.若元素的入栈顺序为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.4043 / 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.1811.在下图中，从顶点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 B.2 D.4 )44 / 10014.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是()15.若需高效地查询多关键字文件，可以采用的文件组织方式为( A.顺序文件 C.散列文件 B.索引文件 D.倒排文件)二、填空题（本大题共10小题，每小题2分，共20分） 请每小题的空格中填上正确答案。错填、不填均无分。 16.下面程序段的时间复杂度为___________。 sum=1； for（i=0；sum&n;i++） sum+=1； 17.已知链表结点定义如下： typedef struct node{ char data［16］； struct node } 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= k=m; while (k&n) { while(a［k］&=0&&k&n) k= if(k&n)47 / 100(2)；(3)；{ temp=a［k］； a［k］=a［m］； a［m］= m= } } } (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) substr(t,s,1,1); substr(s,s,2,strlen(s)-1); f31(s); return strcat(s,t);48 / 100(4) ；；(5)} main( ) { char str[100]= ''String''; printf(''%s\n'',f31(str)); } (1)请写出执行该程序后的输出结果； (2)简述函数f31的功能。 32.下面程序实现插入排序算法。 typedef struct{ I }SeqL void InsertSort(SeqList R［］,int n) {/* 待排序列保存在R［1..n］中*/ SeqList x； int i，j，k，lo,hi, for (i=2；i&=n；i++) { (1) lo=1； hi=i-l; while (lo&=hi) { mi=(lo+hi)/2; if ( (2) ) ；if (R［mi］.key&x.key) hi=mi-l; else lo=mi+l; } if (mi=lo) k=i -49 / 100else k=i - mi-1; for (j=0；j&k；j++) (3) R［i-j］=x； } } 在空白处填写适当的内容，使该程序功能完整。 (1) (2) (3) 33.设有单链表类型定义如下： typedef struct node { struct node * } *LinkL 阅读下列算法，并回答问题： void f33(LinkList head, int A, int B) { LinkList p=NULL; While (head !=NULL) { if (head-&data&A&&head-&data&B) p= head=head-& } if (p !=NULL) printf(&%d\n&,p-&data); } (1)已知链表h如下图所示，给出执行f33(h，5，8)之后的输出结果；50 / 100；(2)简述算法f33的功能。 五、算法设计题（本题10分） 34.已知二叉树的定义如下： typedef struct node{ struct node *lchild, }*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!=head4．若元素的入栈顺序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i(1&=i&=n) 个元素是(D) A.n-i B.n-i+l C.n-i+251 / 100D.无法确定5．串匹配算法的本质是(C) A.串复制 B.串比较 C.子串定位 D.子串链接6．设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址 为1，每个元素占一个字节空间，则a85的地址为(C) A.13 B.18 C.33 D.407．若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是(B) A.树中没有度为2的结点 C.树中非叶结点均只有左子树 B.树中只有一个根结点 D.树中非叶结点均只有右子树8．若根结点的层数为1，则具有n个结点的二叉树的最大高度是(A) A.n B. ?log2 n ? ? ? C. ?log2 n ? +1 ? ? D.n/29．在图G中求两个结点之间的最短路径可以采用的算法是(A) A.迪杰斯特拉（Dijkstra）算法 C.普里姆(Prim)算法 B.克鲁斯卡尔（Kruskal）算法 D.广度优先遍历(BFS)算法10．下图G=(V,E)是一个带权连通图，G的最小生成树的权为(D) A.15 B.16 C.17 D.1811．在下图中，从顶点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 712．如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是(B) A.不稳定的 B.稳定的 C.基于交换的 D.基于选择的13．设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%1352 / 100构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为(C) A.1 B.2 C.3 D.414．已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是(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 * } LinkStrN 如果每个字符占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对应的图形表示。 答：A B x a L b y28．已知二叉树如下：54 / 100a b e f请画出该二叉树对应的森林。 答：c g h jd k29．请回答下列问题： (1)英文缩写DAG的中文含义是什么？(2)请给出下面DAG图的全部拓扑排序。答：(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&n){55 / 100while(a[k]&=0&&k&n) k= (3); if(k&n){ temp=a[k]; a[k]=a[m]; a[m]= (4); m= (5);} } 答：(1)0 (2)m+1 (3)k+1 (4)temp}(5)m+131．阅读下列程序，并回答问题： #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{ I }SeqL void InsertSort(SeqList R[],int n){ /*待排序列保存在R［1..n］中*/ SeqL int i,j,k,lo,hi,56 / 100 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)) if (R[mi].key&x.key) hi=mi-l;else lo=mi+l; } if(mi=lo) k=i- else k=i-mi-1; for (j=0;j&k;j++) (3); 答：(1)x=R[i] (2) R[mi].key==x.key } }R[i-j]=x;在空白处填写适当的内容， 使该程序功能完 整。(3) R[i-j]=R[i-j-1]57 / 10033．设有单链表类型定义如下： typedef struct node { struct node * } *LinkL 阅读下列算法，并回答问题： void f33(LinkList head, int A, int B){ LinkList p=NULL; while (head !=NULL){ if (head-&data&A&&head-&data&B) p= head=head-& } if (p !=NULL) printf(&%d\n&,p-&data); } (1)已知链表h如下图所示，给出执行f33(h，5，8)之后的输出结果；(2)简述算法f33的功能。 答：(1)7 (2)输出链表h中（若存在）最后一个大于A到小于B的值。五、算法设计题（本题10分） 34.已知二叉树的定义如下： typedef struct node{ struct node *lchild, * }*B 编写递归算法求二叉树的高度。函数原型为：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+158 / 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． 假设以数组 A[60]存放循环队列的元素， 其头指针是 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．1039B．线性表 D．再入表 ）10．下列数据结构中，不属于二叉树的是（ A．B 树 C．二叉排序树B．AVL 树 D．哈夫曼树 ）11．对下面有向图给出了四种可能的拓扑序列，其中错误的是（ ．．A．1，5，2，6，3，4 C．5，1，6，3，4，2B．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．v1，v2，v5，v4，v3，v7，v6 D．v1，v2，v5，v6，v7，v3，v4B．归并排序 D．直接插入排序14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值 32 时，查 找成功需要的比较次数是（ A．2 C．4 15．采用 ISAM 组织文件的方式属于（ A．链组织 C．散列组织 ） B．3 D．8 ） 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、 18、 7 和 16 的结点构造一棵哈夫曼(Huffman)树， 用 13、 30、 该树的带权路径长度为_________。 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 DataT struct node * } * LinkL void f30( LinkList Ls ) { LinkList p, q = Ls-& if ( q && q-&next ) { Ls-&next = q-& p=q62 / 100{while ( p-&next ) p = p-& p-&next = 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’ 则函数的返回值是什么?若调用语句是 )， 则函数的返回值是什么? (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&i；j++) if(A[j]&A[j+1]){ x=A[j]； A[j]=A[j+l]； A[j+1]=x； f31(” abcde”” ， abcde” )，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 }*BiTree； 请编写递归函数 SumNodes(BiTree T)，返回二叉树 T 的结点总数。 *lchild，*rchild；全国 2010 年 1 月高等教育自学考试 数据结构试题及参考答案 课程代码：02331一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未 选均无分。 1．若一个算法的时间复杂度用 T(n)表示，其中 n 的含义是（ A A．问题规模 C．循环层数 2．具有线性结构的数据结构是（ A．树 C．栈和队列 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 个元素，则队列的尾指针值为 （ A．3 C．50 B ） B．37 D．97 B ）6．若栈采用链式存储结构，则下列说法中正确的是（ A．需要判断栈满且需要判断栈空 B．不需要判断栈满但需要判断栈空 C．需要判断栈满但不需要判断栈空65 / 100D．不需要判断栈满也不需要判断栈空 7．若串 str=”Software”，其子串的数目是（ D A．8 C．36 B．9 D．37 ）8．设有一个 10 阶的下三角矩阵 A，采用行优先压缩存储方式，all 为第一个元素，其存储地址为 1000，每个元素占 一个地址单元，则 a85 的地址为 A．1012 C．1032 9．允许结点共享的广义表称为（ D A．纯表 C．递归表 ） B．线性表 D．再入表 ） （ C ）B．1017 D．103910．下列数据结构中，不属于二叉树的是（ A A．B 树 C．二叉排序树B．AVL 树 D．哈夫曼树 C ）11．对下面有向图给出了四种可能的拓扑序列，其中错误的是（ ．．A．1，5，2，6，3，4 C．5，1，6，3，4，2B．1，5，6，2，3，4 D．5，1，2，6，4，3 D ）12．以 v1 为起始结点对下图进行深度优先遍历，正确的遍历序列是（A．v1，v2，v3，v4，v5，v6，v7 C．v1，v2，v3，v4，v7，v5，v6 13．下列排序算法中不稳定的是（ A A．快速排序 C．冒泡排序B．v1，v2，v5，v4，v3，v7，v6 D．v1，v2，v5，v6，v7，v3，v4 ） B．归并排序 D．直接插入排序14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值 32 时，查66 / 100找成功需要的比较次数是（ A．2 C．4B） B．3 D．8 ） B．顺序组织 D．索引组织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______。23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是_10,42,12,94,55,01,46,17。 24．高度为 3 的 3 阶 B-树最少的关键字总数是__13_______。67 / 100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 DataT struct node *68 / 100{} * LinkL void f30( LinkList Ls ) { LinkList p, q = Ls-& if ( q && q-&next ) { Ls-&next = q-& p=q while ( p-&next ) p = p-& p-&next = 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； k=n-l；69 / 100while(k&0){ i=k； k=0； for(j=O；j&i；j++) if(A[j]&A[j+1]){ x=A[j]； A[j]=A[j+l]； A[j+1]=x； 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 请在空白处填写适当内容，使该程序功能完整。70 / 100；(1) (2) (3)五、算法设计题(本题 10 分) 34．已知二叉树采用二叉链表存储，其结点结构定义如下： typedef struct Node{ ElmType data； struct Node }*BiTree； 请编写递归函数 SumNodes(BiTree T)，返回二叉树 T 的结点总数。 *lchild，*rchild；全国 2009 年 10 月高等教育自学考试 数据结构试题 课程代码：02331一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未 选均无分。 1．按值可否分解，数据类型通常可分为两类，它们是（ A．静态类型和动态类型 C．原子类型和结构类型3 2）B．原子类型和表类型 D．数组类型和指针类型 ）2． 对于三个函数 f(n)=2008n +8n +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； B．p-&next=r； C．r-&next=q； D．r-&next=q； q-&next=r-&next； r-&next=q； r-&next=q；）q-&next=r-&next； p-&next=r；q-&next=r-&next； p-&next=r；q-&next=r-&next； ）4．若进栈次序为 a，b，c，且进栈和出栈可以穿插进行，则可能出现的含 3 个元素的出栈序列个数是（ A．3 B．571 / 100C．6D．75．假设以数组 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 12．如图所示的有向图的拓扑序列是（ A．c，d，b，a，e B．c，a，d，b，e72 / 100B．8 D．22 ）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) 14．分块查找方法将表分为多块，并要求（ A．块内有序 C．各块等长 15．便于进行布尔查询的文件组织方式是（ A．顺序文件 C．散列文件 B．(5，1，4，3，2，6，7，8) D．(8，7，6，5，4，3，2，1) ） B．块间有序 D．链式存储 ） B．索引文件 D．多关键字文件 ）二、填空题（本大题共 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27．由字符集{s，t，a，e，I}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为 ，请根据该哈夫曼树进行译码，写出原来的电文。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&g-&n； visited[i]=0； for (i=k=0； i&g-&n; i++) if (visited[i]= =0) { k++； DFS(g，i)； } return k； } i++)／*g-&n 为图 g 的顶点数目*／31．假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node { 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, p=A-& q=B-& while (p && q) { if (p-&id&q-&id) p=p-& else if (p-&id&q-&id) q=q-& else { if (p-&score&60) if (q-&score&60) p-&score=q-& else p-&score=60; p=p-& q=q-& } } } 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, 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); } 33．二叉排序树的存储结构定义为以下类型： typedef int KeyT typedef struct node { KeyType InfoT /*关键字项*/ /*其它数据项*/struct node *1child, * /*左、右孩子指针*/ } 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) if (T-&key&x)return T; return f33(T-& rchild, x); }五、算法设计题（本题 10 分）77 / 10034．假设线性表采用顺序存储结构，其类型定义如下： #define ListSize 100 typedef struct { int data［ListSize］; } SeqList, *T编写算法，将顺序表 L 中所有值为奇数的元素调整到表的前端。2009 年 10 月 数据结构 一、单项选择题（本大题共 15 小题,每小题 2 分,共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。 错选、 多选或未选 均无分。 1．按值可否分解,数据类型通常可分为两类,它们是（ C ） A．静态类型和动态类型 B．原子类型和表类型 C．原子类型和结构类型 D．数组类型和指针类型 3 2 3 2 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 ） A．3 B．5 C．6 D．7278 / 100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 。 22． 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中 边 的数目正相关。79 / 100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}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段 电文的哈夫曼编码为 ,请根据该哈夫曼树进行译码,写出原来的电文。 答 案：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&g-&n; i++) if (visited[i]= =0) { k++； DFS(g,i)； } return k；80 / 100} 31．假设学生成绩按学号增序存储在带头结点的单链表中,类型定义如下： typedef struct Node { /*学号*/ 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, p=A-& q=B-& while (p && q) { if (p-&id&q-&id) p=p-& else if (p-&id&q-&id) q=q-& else { if (p-&score&60) if (q-&score&60) p-&score=q-& else p-&score=60; p=p-& q=q-& } } }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, ls=strlen(s);81 / 100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); } 33．二叉排序树的存储结构定义为以下类型： typedef int KeyT typedef struct node { KeyT /*关键字项*/ InfoT /*其它数据项*/ struct node *1child, * /*左、右孩子指针*/ } 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) if (T-&key&x)return T; return f33(T-& rchild, x); }五、算法设计题（本题 10 分） 34．假设线性表采用顺序存储结构,其类型定义如下： #define ListSize 100 typedef struct { int data［ListSize］; } SeqList, *T82 / 100编写算法,将顺序表 L 中所有值为奇数的元素调整到表的前端。2007 年 1 月高等教育自学考试全国统一命题考试数据结构试题课程代码 2331一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）83 / 100在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选 均无分。 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．对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（ A．求一个顶点的邻接点 B．求一个顶点的度84 / 100）C．深度优先遍历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．一个类型 15．稀疏索引是指在文件的索引表中（ A．为每个字段设一个索引项 C．为每组字段设一个索引项B．一组记录 D．一个文件 ） B．为每个记录设一个索引项 D．为每组记录设一个索引项二、填空题（本大题共 10 小题，每小题 2 分，共 20 分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．链式存储结构的特点是借助_______来表示数据元素之间的逻辑关系。 17． 假设带头结点的非空单循环链表中仅设尾指针 L， 则在第 1 个结点之前插入指针 s 所指结点的语句依次是_______； _______。 18．无表头结点的链队列 Q 为空的条件是_______。 19．不含任何字符的串称为_______。 ． 20． 假设按行优先顺序将一个 20 阶的三对角矩阵 A 压缩存储在一维数组 Q 中， 其中 Q[0]存放矩阵的第 1 个元素 a1,1，85 / 100那么矩阵元素 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&L-&i++) { for(j=0;j&k && L-&data[i]!=L-&data[j];j++); if(j==k) { if(k!=i)L-&data[k]=L-&data[i]; k++; } } 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DataTypee;if (!QueueEmpty(Q)){ e=DeQueue(Q); f 31(Q); EnQueue(Q,e); } } (1) (2) 32．已知树的存储结构为孩子兄弟链表，其类型定义如下： typedef struct CSTNode { struct CSTNode leftmostchild,* } CSTNode, *CST 阅读函数 f 32,并回答下列问题： （1）对于如图所示树，写出函数调用 f 32(T)