全国高等教育自学测验考试数据结构试题

《全国高等教育自学测验考试数据结构试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国2007年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内.错选、多选或未选均无分.矚慫润厲钐瘗睞枥庑赖。1.下面程序段的时间复杂度为()s=0；for(i=1；i

2、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)％mC.(rea

3、r-length+m-1)％mD.(rear-length)％m5.通常将链串的结点大小设置为大于1是为了()A.提高串匹配效率B.提高存储密度C.便于插入操作D.便于删除操作6.带行表的三元组表是稀疏矩阵的一种()A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构7.表头和表尾均为空表的广义表是()A.()B.(())C.((()))D.(()，())8.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为()A.n-1B.nC.n+lD.2n9.为便于判别有向图中是否存在回路，可借助于()A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.

4、拓扑排序算法10.连通网的最小生成树是其所有生成树中()A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树════════════════════════════════════════════════════════════════════-本套试题共分6页，当前页是第6页-11.按排序过程中依据的原则分类，快速排序属于()A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法12.下列关键字序列中，构成小根堆的是()A.{84，46，62，41，28，58，15，37}B.{84，62，58，4

5、6，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.4B.5C.6D.714.假设在构建散列表时，采用线性探测解决冲突.若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为()A.n-1B.nC.n+lD.n+215.散列文件也称为()A.顺序文件B.索引文件C.直接存取文件D.间接存取文件二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案.错填

6、、不填均无分.16.数据的逻辑结构描述数据元素之间的_________________，与存储方式无关.17.在一个长度为100的顺序表中删除第10个元素时，需移动___________________个元素.酽锕极額閉镇桧猪訣锥。18.队列的队尾位置通常是随着______________操作而变化的.19.两个空串联接得到的串的长度为___________________.20.设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素a11存储在B[0]，元素a52存储在B[11]，则矩阵元素a36存储在B[______________]中.彈贸摄尔霁毙攬砖卤庑。21.

7、已知一棵哈夫曼树含有60个叶子结点，则该树中共有________________个非叶子结点.22.如图所示的有向图中含有_______________个强连通分量.23.已知一组关键字为{15，36，28，97，24，78，47，52，13，86}，其中每相邻两个关键字构成一个有序子序列.对这些子序列进行一趟两两归并的结果是______________.謀荞抟箧飆鐸怼类蒋薔。24.从空树起，依次插入关键字1l，27，35，48，52，66和73构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为______