《数据结构导论自考题》由会员分享，可在线阅读，更多相关《数据结构导论自考题（15页珍藏版）》请在金锄头文库上搜索。
1、2数据结构导论自考题-2（总分100,做题时间90分钟）一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的。1.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）A存储结构B存储实现C.逻辑结构D.运算实现SSS_SIMPLE_SINABCD分值：2答案:C2.所有的存储结点存放在一个连续的存储空间，该存储方式是（）存储方式。A. 顺序B.链式C索引D散列SSS_SIMPLE_SINABCD分值：2答案:A解析本题主要考查的知识点是顺序存储方式。要点透析顺序存储方式是指所有存储结点存放在一个连续的存储区里。利用 结点在存储器中的相对位置来表示数据元素之间的逻辑关系。3
2、.设线性表有n个元素，以下操作中，（）在顺序表上实现比在链表上实现效率更咼。A. 输出第i （lWiWn）个元素值B.交换第1个元素与第2个元素的值C.在第i个元素前插入一个元素 D.删除第i个元素SSS_SIMPLE_SINABCD分值：2答案:A解析本题主要考查的知识点为顺序表和链表。要点透析由于顺序表具有随机存取特性，所以和链表相比输出第i个元素时 效率很高。本题答案为A。4.与单链表相比，双链表的优点之一是（）A.插入、删除操作更简单 B.可以进行随机访问C.可以省略表头指针或表尾指针 D.前后访问相邻结点更灵活SSS_SIMPLE_SINABCD分值：2答案:D5.循环队列的队满条件
3、为（）A. （CQ.rear+l）%maxsize=（CQ.fro nt+l）%maxsizeB. （CQ.rear+l）%maxsize二二CQ.fro nt+1C. （CQ.rear+l）%maxsize二二CQ.fro ntD. CQ.rear二二CQ.frontSSS_SIMPLE_SINABCD分值：2答案:C解析本题主要考查的知识点是循环队列的队满条件。要点透析约定循环队列的队头指针指示队头元素在数组中实际位置的前一个 位置，队尾指针指示队尾元素在数组中的实际位置。当队尾指针“绕一圈”后 赶上队头指针时，视为队满。6.数组A0.50.5的每个元素占5个字节，将其以列为主序存储在起始
4、地 址为1000的内存单元中，则元素A55的地址是（）A. 1175 B. 1180C. 1205 D. 1210SSS_SIMPLE_SINABCD分值：2答案:A7.若二叉树（如图所示）采用二叉链表存储结构，要交换其所有分支结点左右子树 的位置，最合适的遍历方法是（）A.先序遍历B.中序遍历C.后序遍历D.按层次遍历SSS_SIMPLE_SINABCD分值：2答案:A解析本题主要考查的知识点是二叉链表存储结构。要点透析交换二叉树的左右子树的过程可用递归方法完成，第1步将根结点 的左右子树交换，第2步在左子树中递归调用交换函数，第3步在右子树中递 归调用交换函数。因此，采用先序遍历的方法最合
5、适。8.则a的地址为45设有一个10阶的对称矩阵A，米用压缩存储方式以行序为主序存储，a为第一 个元素，其存储地址为0,每个元素占有1个存储地址空间, ( )A. 13 B. 19C. 17 D. 36SSS_SIMPLE_SINABCD分值：2答案:B9.在有向图中，所有顶点的入度之和是所有顶点出度之和的()A. 0.5 倍 B. 1 倍C. 2倍 D. 4倍SSS_SIMPLE_SINABCD分值：2答案:B10.设无向图G中顶点数为n,则图G最多拥有边的条数是()A. nB.n-1C. n(n1)/2 D. n(nT)SSS_SIMPLE_SINABCD分值：2答案:C解析本题主要考查的
6、知识点是无向图中边的条数。要点透析在无向图为完全图时，取得的边数最多，此时任意两个顶点间都有 直接边，边的条数为：(n-1)+2+1二n(n-1)/2。11.A. v1C. v在图中，从顶点v出发，按深度优先遍历图的顶点序列是(B. v1D. vSSS_SIMPLE_SINABCD分值：2答案:C解析本题主要考查的知识点是深度优先遍历。要点透析连通图深度优先搜索的基本思想是：假定图中某个顶点v为出发 点。首先访问出发点，然后任选一个v的未访问过的邻接点V,以v为新的出 发点继续进行深度优先搜索，直至图中所有顶点都被访问过。J12.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相
7、同，假 设采用顺序查找来确定结点所在的块时，每块应分结点的个数是（）A. 10 B. 25C. 6 D. 625SSS_SIMPLE_SINABCD分值：2答案:B解析本题主要考查的知识点是分块查找。要点透析分块查找一般都是要求每个块的存储空间大小是一样的，而且块数 不能太多，每个块也不要太小，否则就成了顺序查找了。由于10和6都不能被 625整除，不宜作为划分块的标准，而如果采用625，则每个块只有一个元素， 这样就失去了分块的意义了。13.从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序 序列的正确位置上，应采用（）A归并排序B插入排序C.快速排序D.选择排序SSS_S
8、IMPLE_SINABCD分值：2答案:B14.具有24个记录的序列，采用冒泡排序最少的比较次数是（）A. 1 B. 23C. 24 D. 529SSS_SIMPLE_SINABCD分值：2答案:B解析本题主要考查的知识点是冒泡排序。要点透析冒泡排序的思想为：在每一次排序过程中，通过相邻元素的交换, 将当前没有排好序中的最大（小）移到数组的最右（左）端。在递增（减）顺序中， 排序所需次数最小，24个记录需排23次。15.用某种排序方法对序列（25, 84，21，47，15，27，68，35，20）进行排序，记 录序列的变化情况如下：2584214715276835202015212547276
9、83584152021253527476884152021252735476884则采用【的排序方法去是（)A.直接选择排序B.冒泡排序C.快速排三序D.二路归并排序SSS_SIMPLE_SINABCD分值：2答案:C解析本题主要考查的知识点是快速排序。要点透析此题可使用排除法。选项A，若使用直接选择排序，第一个元素应 为15,而给出的是25,所以排除。选项B、C两种排序方法，同属交换排序 法，观察发现，第一趟排序，有明显的分组情况（按25分为两组），可得最佳答 案应为C。题目没有采用合并的方式。二、填空题 16.空间复杂度是对一个算法在运行过程中临时占用的度量。分值：2答案:存储空间大小17
10、.在数据结构中，数据的逻辑结构分为集合、树形结构和图结构等四类。SSS_FILL分值：2答案:线性结构18.对顺序表执行插入操作，其插入算法的平均时间复杂度为SSS_FILL分值：2答案：O(n)19.如图所示，设输入元素的顺序是A、B、C、D,通过栈的变换，在输出端可得到 各种排列。若输出序列的第一个元素为D，则输出序列为。SSS_FILL分值：2答案:DCBA20.队列中，新加入的数据元素插在。分值：2答案:队尾21.设有二维数组in t M1020，每个元素(整数)占2个存储单元，数组的起始地址为2000，元素M510的存储位置为，M819的存储位置为SSS_FILL分值：2答案：222
11、0235822.树在数据结构中常采用孩子链表表示法、双亲表示法三种存储结构表/示OSSS_FILLZ ；I?分值：2答案:孩子兄弟链表表示法23.答案：724.具有n个叶子结点的哈夫曼树，其结点总数为分值：2答案：2n-l 25.一个具有n个顶点的有向完全图的弧数为分值：2答案:n(n-l)26.已知有向图G=(V，E)，其中：V二v， v，v，v，v，v，v1234567E二Vv， v ，Vv， v ，Vv， v ，Vv， v ，Vv， v ，Vv， v121314253736，Vv， v ，Vv， v ，Vv， v G的拓扑序列是7。67SSS_FILL分值：2答案：v v v v v v
12、 v134625727.方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在 其最终位置上。分值：2答案:快速排序分值：2答案:O(nlog n)2三、应用题 29.对于图所示二叉树，分别写出其先序遍历、中序遍历和后序遍历的结点访问序 列。SSS_TEXT_QUSTI 斗 |分值：6答案：先序遍历：ABDEFC中序遍历：BFEDAC后序遍历：FEDBCA30.有一份电文中共使用五个字符：a，b，c，d，e,它们的出现频率依次为8, 14，10，4，18,请构造相应的哈夫曼树。SSS_TEXT_QUSTI 彳 I分值：6答案：所求哈夫曼树如图所示：31.若某无向图G的邻接表如图所示，试
13、给出以顶点V为出发点，按广度优先搜索 所产生的一棵生成树。SSS_TEXT_QUSTI 斗 |分值：6答案：所求生成树如图所示：32.从一个空的二叉排序树开始，依次插入关键字25、13、15、34、7、20、37, 试分别画出每次插入关键字后的二叉排序树。SSS_TEXT_QUSTl| 斗 |分值：6答案：所求二叉排序树如图所示：33.已知一组键值序列(32, 44, 38, 65, 53, 42, 29, 57)，试采用堆排序法对该 组序列作升序排序，给出建立的初始堆以及第一次输出堆元素后筛选调整的 堆。SSS_TEXT_QUSTI 彳 |分值：6答案：所求初始堆如图(a)所示:输出堆顶后的调整堆如图(b)所示:四、算法设计题 34.若循环单链表长度大于1, P为指向链表中某结点的指针，试编写一算法删除P 结点的前驱结点。分值：7答案：Node*delete(p)Node*P;Node *q, *r;q=p； while(q-nex t!二p) q二q-nex t;r=q; while(r-nex t!二q) r=r-nex t;r-nex t二p; free(q); retu rn(p);
