数据结构各年联考试题.doc

全国2007年10月高等教育自学考试数据结构试题1.下面程序段的时间复杂度为( ) s=0； for(i=1；in；i++) for(j=1；ji；j++) s+=i*j； A.O(1) B.O(logn) C.O(n) D.O(n2) 2.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向 另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为( ) 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.栈 B.队列 C.树 D.图 4.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队 尾元素的下一个存储位置，则队头元素所在的存储位置为( ) A.(rear-length+m+1)％m B.(rear-length+m)％m C.(rear-length+m-1)％m D.(rear-length)％m 5.通常将链串的结点大小设置为大于1是为了( ) A.提高串匹配效率 B.提高存储密度 C.便于插入操作 D.便于删除操作 6.带行表的三元组表是稀疏矩阵的一种( ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 7.表头和表尾均为空表的广义表是( ) A.() B.(()) C.((())) D.(()，()) 8.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( ) A.n-1 B.n C.n+l D.2n 9.为便于判别有向图中是否存在回路，可借助于( ) A.广度优先有哪些信誉好的足球投注网站算法 B.最小生成树算法 C.最短路径算法 D.拓扑排序算法 10.连通网的最小生成树是其所有生成树中( ) A.顶点集最小的生成树 B.边集最小的生成树 C.顶点权值之和最小的生成树 D.边的权值之和最小的生成树 11.按排序过程中依据的原则分类，快速排序属于( ) A.插入类的排序方法 B.选择类的排序方法 C.交换类的排序方法 D.归并类的排序方法 12.下列关键字序列中，构成小根堆的是( ) 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的有序表中进行二分查找时，所需进行的关键字比较次数最多为( ) A.4 B.5 C.6 D.7 14.假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义 词，则查找其中最后插入的关键字时，所需进行的比较次数为( ) A.n-1 B.n C.n+l D.n+2 15.散列文件也称为( ) A.顺序文件 B.索引文件 C.直接存取文件 D.间接存取文件二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.数据的逻辑结构描述数据元素之间的_________________，与存储方式无关。 17.在一个长度为100的顺序表中删除第10个元素时，需移动___________________个元素。 18.队列的队尾位置通常是随着______________操作而变化的。 19.两个空串联接得到的串的长度为___________________。 20.设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素a11存储在B[0]，元素a52存储在B[11]，则矩阵元素a36存储在B[______________]中。 21.已知一棵哈夫曼树含有60个叶子结点，则该树中共有________________个非叶子结点。22.如图所示的有向图中含有 _______________个强连通分量。23.已知一组关键字为{15，36，28，97，24，78，47，52，13，86}，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是______________。 24.从空树起，依次插入关键字1l，27，35，48，52，66和73构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为____________________。 25.控制区间和控制区域是________________文件的逻辑存储单位。三、解