2007年10月全国自考数据结构试题及答案.pdf

2007 年10 月全国自考数据结构试题 课程代码：02331 一、单项选择题（本大题共15 小题，每小题2 分，共30 分） 1．下面程序段的时间复杂度为(D) s=0 ； for(i=1；in ；i++) for(j=1 ；ji ；j++) s+=i*j ； A.O(1) B.O(logn) 2 C.O(n) D.O(n ) 2 ．已知指针p 和q 分别指向某单链表中第一个结点和最后一个结点。假设指针s 指向另一 个单链表中某个结点，则在s 所指结点之后插入上述链表应执行的语句为(A) A.q-next=s-next ；s-next=p ； B.s-next=p ；q-next=s-next ； C.p-next=s-next ；s-next=q ； D.s-next=q ；p-next=s-next ； 3 ．在计算机内实现递归算法时所需的辅助数据结构是(A) A.栈 B. 队列 C.树 D. 图 4 ．假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear 指向队尾元 素的下一个存储位置，则队头元素所在的存储位置为(B) A.(rear-length+m+1) ％m B.(rear-length+m) ％m C.(rear-length+m-1)％m D.(rear-length) ％m 5 ．通常将链串的结点大小设置为大于1 是为了(B) A.提高串匹配效率 B.提高存储密度 C.便于插入操作 D.便于删除操作 6 ．带行表的三元组表是稀疏矩阵的一种(A) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 7 ．表头和表尾均为空表的广义表是(B) A.() B.(()) 1 / 8 C.((())) D.(() ，()) 8．用二叉链表表示具有n 个结点的二叉树时，值为空的指针域的个数为(C) A.n-1 B.n C.n+l D.2n 9 ．为便于判别有向图中是否存在回路，可借助于(D) A.广度优先搜索算法 B.最小生成树算法 C.最短路径算法 D.拓扑排序算法 10．连通网的最小生成树是其所有生成树中(D) A.顶点集最小的生成树 B.边集最小的生成树 C.顶点权值之和最小的生成树 D.边的权值之和最小的生成树 11．按排序过程中依据的原则分类，快速排序属于(C) A.插入类的排序方法 B.选择类的排序方法 C.交换类的排序方法 D.归并类的排序方法 12．下列关键字序列中，构成小根堆的是(D) A.{84 ，46，62，41，28，58，15，37} B.{84，62，58，46，41，37，28，15} C.{15，28，46，37，84，41 ，58，62} D.{15，28，46，37，84，58，62，41} 13．在长度为32 的有序表中进行二分查找时，所需进行的关键字比较