[教育学]2007-2011数据结构试卷解析.doc

全国2007年10月高等教育自学考试 数据结构.下面程序段的时间复杂度为 s=0； for(i=；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)％mB.(rear-length+m)％m(rear-front+m)％mC.(rear-length+m-1)％mD.(rear-length)％m 5.通常将链串的结点大小设置为大于1是为了链串的结点大小A.提高串匹配效率B.提高存储密度 C.便于插入操作D.便于删除操作6.带行表的三元组表是稀疏矩阵的一种 A.顺序存储结构B.链式存储结构 C.索引存储结构D.散列存储结构7.表头和表尾均为空表的广义表是 A.() 空表不能做运算 B.(()) C.((()))=C head(C)=(( )) tail(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.队列的队尾位置通常是随着操作而变化的。9.两个空串联接得到的串的长度为。20.设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素a存储在B[]，元素a52存储在B[11]，则矩阵元素a36存储在B[]中。a36实际存储在a63中。且存储中每行只从ai 1存储到ai i每行i个数字，因而到a63有1+2+3+4+5+3=18，因为数组下标从0开始，第18个下标为B[17]。 21.已知一棵哈夫曼树含有60个叶子结点，则该树中共有个非叶子结点。哈夫曼树哈夫曼树22.如图所示的有向图中含有个强连通分量。23.已知一组关键字为{15，36，28，97，24，78，47，52，13，86}，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是24.从空树起，依次插入关键字1l，27，35，48，52，66和73构造所得的二叉排序树，在等概率查找的假设下，查找 25.控制区间和控制区域是文件的逻辑存储单位。(本大题共4小题，每小题5分，共20分26.利用广义表的head和tail操作，可从广义表 L=((a，b)，(c，d)) 中分解得到原子c，其操作表达式为 head(head(tail(L)))； 分别写出从下列广义表中分解得到b的操作表达式。 (1)L1=(a.，b，c，d)； (2)L2=(((a)，(b)，(c)，(d)))。 (2) head(