数据结构样题及答案.doc

一填空题（每题2 分，共20 分）；1. 数据结构算法中，通常用时间复杂度和_空间复杂度_两种方法衡量其效率。2. 下面程序段的时间复杂度为_ O(n2)_。(n1)for(i = 1; i = n; i+)for(j = 1; j = i; j+)x = x + 1;3. 在一个长度为 n 的顺序表中第i 个元素（1=i=n）之前插入一个元素时，需向后移动_ n-i+1_个元素。4. 在 n 个结点的单链表中要删除已知结点*p，需找到它的_前驱_。5. 在具有 n 个元素空间的循环队列中，队满时共有_n-1_个元素。6. 两个串相等的充分必要条件是_串长相等且对应字符相等_。7. 具有 256 个结点的完全二叉树的深度为_9_。8. G 是一个非连通无向图，共有36 条边，则该图至少有_9_个顶点。 边数=N(N-1)/29. 在顺序表（8,11,15,19,21,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为_4_。10. 直接插入排序用监视哨的作用是_始终存放待插入的记录，免去查找过程中每一步都要检测整个表是否查找完毕_。二单项选择题1. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表2. 设 a1、a2、a3 为3 个结点，则如下的链式存储结构称为：(A)表元编号 结点表元间关系1a132a213a32A循环链表 B单链表 C双向循环链表 D双向链表3. 有六个元素 6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（B）A. 5 4 3 6 1 2 B. 3 4 6 5 2 1 C. 4 5 3 1 2 6 D. 2 3 4 1 5 64. 若栈采用顺序存储方式存储，现两栈共享空间 V1.m，topi代表第i 个栈( i =1,2)栈顶，栈1 的底在v1，栈2 的底在Vm，则栈满的条件是（B ）。A. top2-top1|=0 B. top1+1=top2C. top1+top2=m D. top1=top25. 数组用来表示一个循环队列，front 为当前队列头元素的前一位置，rear 为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为(D)A. rearfront B.（nfrontrear）% nC. nrearfront D.（nrearfront）% n6. 设栈 S 和队列Q 的初始状态为空，元素e1，e2，e3，e4,e5 和e6 依次通过栈S，一个元素出栈后即进队列Q，若6 个元素出队的序列是e2，e4,e6,e5，e3,e1 则栈S 的容量至少应该是(B )。A 6 B. 4 C. 3 D. 27. 设有数组 Ai,j，数组的每个元素长度为3 字节，i 的值为1 到8 ，j 的值为1 到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为( B)。A. BA+141 B. BA+180 C. BA+222 D. BA+2258. 已知广义表 L=(x,y,z),a,(u,t,w)，从L 表中取出原子项t 的运算是（D）。A. head（tail（tail（L） B. tail（head（head（tail（L）C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）)）9. 一棵树高为 K 的完全二叉树至少有（C）个结点?A2k 1 B. 2k-1 1 C. 2k-1 D. 2k10. 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（C ）的二叉树。A空或只有一个结点 B任一结点无左子树C高度等于其结点数 D任一结点无右子树11. 无向图 G=(V,E),其向V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是(A ）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b12. 下面关于求关键路径的说法不正确的是（ B）。A求关键路径是以拓扑排序为基础的B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D关键活动一定位于关键路径上13. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A 的左孩子的平衡因子为 0 右孩子的平衡因子为1,则应作( C) 型调整以使其平衡。A. LL B. LR C. RL D. RR14. 设哈希表长为 14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84 共四个，现要将关键字为49 的结点加到表中，用平方探测再散列法解决冲突，则放入的位置是(D)A8 B3 C5 D915. 对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21（3） 15 21 25 84 47 （4） 15 21 25 47 84则采用的排序是 (A )。A. 选择 B. 冒泡 C. 快速 D. 插入三、判断题（每题1 分，共5 分，正确的打，错误的打）( T) 1数据元素是数据的最小单位。(F ) 2线性表在链式存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。(T ) 3栈和队列的存储方式既可是顺序方式，也可是链接方式。( F) 4带权无向图的最小生成树必是唯一的。(F ) 5排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。四综合题（共 45 分）1. 线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L=23，17，47，05，31，若它以单链表方式存储在下列100119 号地址空间中，每个结点由数据（占2 个字节）和指针（占2 个字节,由大写字母表示）组成，如下所示：100 120 47p23q05r31s17t其中指针 p，q，r，s，t 的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？(共7 分)答：p= 108 q = 116 r =112 s=0 或NULLt= 100 首址= 104 末址=1122. 如果想将输入的一个字符序列逆序输出，如输入“abcdef ”，输出“fedcba”，请分析用线性表、堆栈和队列等方式正确输出的可能性？ (共6 分)答：线性表是随机存储，可以实现，靠循环变量（j-）从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；队列是先进先出，不易实现3. 设二叉树后根遍历为 BAC，画出所有可能的二叉树。(共5 分)4. 有一份电文中共使用 6 个字符:a,b,c,d,e,f,它们的出现频率依次为2,6,7,4,3,5，试写出为这六个字母设计的哈夫曼编码, 并画出对应的哈夫曼树。(共 5. 某田径赛中各选手的参赛项目表如下:姓名参 赛 项ZHAOA B EQIANC DSHUNC E FLID F AZHOUB F设项目A ,B ,，F 各表示一数据元素,若两项目不能同时举行,则将其连线(约束条件).（1）根据此表及约束条件画出相应的图状结构模型,并画出此图的邻接表结构; (共5 分)（2）写出从元素A 出发按“广度优先搜索”算法遍历此图的元素序列. (共3 分)ABDEFC6. 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。(共6 分）7. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：（6 分）(1) 冒泡排序（3 分）第一趟排序结果： 18，25，29，47，12，51,10,58试按上面的描述形式说明排序全过程（动态过程,写出每趟排序后数列的变化结果）要求按递增顺序排序。第一： 18，25，29，47，12，51,10,58第二： 18，25，29，12，47，10，51第三： 18，25，12，29，10，47第四： 18，12，25，10，29第五： 12，18