数据结构考试题

1、一、单项选择1. 数据结构是一门研究非数值计算的程序设计问题中 ，数据元素的、数据信息在计算机中的A 以及一组相关的运算等的课程。 A 操作对象E.计算方法C.逻辑结构D.数据映象 A 存储结构E.关系C.运算D.算法2. 以下数据结构中, D 是线性结构。A .广义表E.二叉树 C.稀疏矩阵 D.串3. 从逻辑上可以把数据结构分为 C两大类。A 动态结构和静态结构E.顺序结构和链式结构C.线性结构和非线性结构D.初等结构和构造型结构4. 以下数据结构中, D 是线性结构。A .广义表E.二叉树C.稀疏矩阵D.串5. 以下数据结构中, D 是非线性结构。A 栈E.二叉树C.队列D.字符串6.

2、数据结构DS(Data Struct)可以被形式地定义为DS= ( D, R),其中D是_B_的有限集合，R是D上的有限集合。 A 算法E.数据元素C.数据操作D.数据对象 A 操作E.映象C.存储D.关系7. 线性表的顺序存储结构是一种丄的存储结构,线性表的链式存储结构是一种的B存储结构。A .随机存取E.顺序存取 C.索引存取 D.散列存取8. 线性表的逻辑顺序与存储顺序总是一致的，这种说法_BA.正确B.不正确9. 下面那一条是顺序存储结构的优点？ (A)A .存储密度大B.插入运算方便C.删除运算方便D.可以方便的用于各种逻辑结构的存储表示10. 线性表采用链式存储结构时,要求内存中可

3、用的存储单元的地址 .A .必须是连续的B.部分地址必须是连续的C. 一定不连续D.连续和不连续都可以,插入一个元素所需要移动元素的平均次数为11. 表长为n的顺序存储的线性表，当在任何位置上插入和删除一个元素的概率相等时 E,删除一个元素所需要移动元素的平均次数为AA. (n-1)/2 B.n C. n+1 D. n-1 E. n/2 F. (n+1)/2 G (n-2)/2 12.带头结点的单链表head为空的判定条件是_B。A. head= =NULLB. head-> next= =NULLC. head-> next= =headD. head!=NULL13. 在一个单

4、链表中,若删除p所指向结点的后继结点,则执行_A_A. p->n ext= p->n ext- >n extB. p=p->n ext; p->n ext= p->n ext- >nextC. p= p->n ext- >n extD. p= p->n ext14. 若已知一个栈的入栈序列是1， 2， 3,A. iB. n=i C. n-i+1，n,其输出序列为p1, p2, p3,，pn,D.不确定若 p1= n,贝U pi 为 C 015.设栈的输入次序为：1 , 2, 3, 4, 5,则不可能是其出栈序列A. 54321 B.

5、45321 C.43512 D. 1234516. 一个涕归算法必须包括BA.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分17.用链接方式存储的队列,在进行删除操作时 DA仅修改头指针B.仅修改尾指针C.头尾指针都要修改D.头尾指针可能都要修改18.数组Am存放循环队列的元素，其头尾指针分别是front和rear,则当前队列的元素个数是A. (rear-fro nt+m)%m B. (fron t-rea 叶m )%mC. fron t-rear+1 D. rear-fr on t+119. 栈和队列的共同特点_。A.都是先进先出B.都是先进后出C.允许在端点插入和删除元素

6、D.没有共同点20. 一个栈的入栈序列a，b, c,A. edcba B. decbad，e,贝U栈的输出序列是 一A.C. dceab D. abcde21.栈的特点是_B_,队列的特点是_AA.先进先出B.先进后出22. 从一个栈顶指针HS的链表中删除一个结点,用x保存被删除的结点值，执行的语句为_CA. x=HS; HS=HS->n extB. HS=HS->n ext; x=HS->data23. 在链队列Q中,插入s所指向的结点执行的语句为 _C_。A. Q.front->n ext=s;B. Q.rear- >n ext=s; Q.rear=sC. s

7、->n ext=Q.rear;Q.rear=sD. s->n ext=Q.fr on t;Q.fro nt=s24. 空串与空格串是相同的，这种说法 _B_。A.正确B.不正确25. 下面关于串的叙述,哪一个是不正确的 _B_。A.串是字符的有限序列B.空串是由空格构成的串C.匹配模式是串的一种重要运算D.串可以采用链式存储结构26. 设有两个串p和q，求q在p中首次出现的位置的运算称作 _B_。A.连接B.模式匹配C.求子串D.求串长27. 若串s='software',其子串的数目为BA. 8B. 37 C. 36 D. 928. 二维数组A中，每个元素A的长度

8、为3个字节，行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内, 该数组按行存放时，数组元素A74的起始地址为_C_。A. SA+141 B. SA+144 C. SA+222 D. SA+22529. 对稀疏矩阵进行压缩存储的目的是_C_.A.便于进行矩阵运算B.便于输入输出C节省存储空间D.降低运算的时间复杂度30.在以下叙述中正确的是BA. 线性表的线性存储结构优于链表存储结构B. 二维数组可以看成是其数据元素为线性表的线性表C. 栈的操作方式是先进先出D. 队列的操作方式是先进后出31.广义表(a),a)的表头为C ,表尾为 C .A. ()B. a C. (a)

9、D. (a) 32.已知广义表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)33.树最适合用来表示 BB.数据之间具有分支层次关系的数据D.无太多关系的数据元素A.有序的数据元素C.无序的数据元素34.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_BA. uwvtsB. vwutsC. wuvts D. wutsv 35.某二叉

10、树的前序遍历结点访问顺序是 abdgcefh,中序遍历的结点访问顺序是 dgbaech，贝U其后序遍历的结点访问顺序是 _DA. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca36. 在一非空二叉树的中序遍历序列中，根结点的右边A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点37. 设m和n是一棵二叉树上的两个结点,在中序遍历,n在m前的条件是CA. n在m的右方B. n是m的祖先C. n在m的左方D. n是m的子孙38. 深度为5的二叉树至多有_C_个结点。A. 16B. 32C. 31D. 1

11、039. 由权(8,2,5,7)的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_DA. 23B. 37C.46D. 4340. 利用二叉链表存储树，则根结点的右指针是_CA.指向最左孩子B.指向最右孩子C.空 D.非空41. 下列存储方式中，哪一个不是树的存储形式？ D .A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法42. 在一个无向图中，所有顶点的度数之和等于所有边数的_C_倍。A. 1/2B. 1C. 2D. 443. 具有n个顶点和多于n-1条边的无向图B.A.有可能是树B. 一定不是树C. 一定是树 D.以上答案都不对44. 具有6个顶点的无向图至少应有

12、_A_条边才能确保是一个连通图。A. 5B. 6C. 7D. 845. 无向图 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),则对该图进行深度优先遍历,得到的序列为:D_A. abecdf B. acfebd C. aebcfd D. aedfcb46. 下述几种排序方法中，要求内存量最大的是 _D_。A.插入排序B.选择排序C.快速排序D.归并排序47. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上 的方法，称为_C_。A.希尔排

13、序 B.起泡排序C.插入排序D.选择排序48. 在待排序的兀素序列基本有序的前提下，效率最咼的排序方法是AA.插入排序B.选择排序 C.快速排序D.归并排序49. 下列排序算法中,哪一个是稳定的排序算法？ B _A.直接选择排序 B.二分法插入排序C.希尔排序D.快速排序50. 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数AA. nB. 2n-1C. 2nD. n-1二、填空题1. 算法的五个重要特性是有穷性，确定性,可行性,输入和输出.2. 数据的树型结构和图（网）状结构合称非线性结构.3. 抽象数据类型的定义仅取决于它的一组逻辑特性,而与数据在计算机中的表示和实现无关.4.

14、 评价算法质量的指标是 正确性，易读性健壮性高效性.5. 数据结构中评价算法的两个重要指标是:时间复杂度和空间复杂度6. 分析下面算法(程序段)，的时间复杂度是 O (mn) 。s=0;for (i=0;i< n;i+)for (j=0;j<m;j+)s+=Bij；7. 当线性表元素的总数基本稳定,且很少进行删除和插入操作时，但是要求以最快的速度存取线性表中的元素,应该采取顺序 存储结构8. 顺序表中逻辑上相邻的元素的物理位置 必定相邻,而单链表中逻辑上相邻的元素的物理位置 不一定相邻.9. 在各个结点查找概率相等的情况下,从n个结点的单链表中查找一个结点，平均要访问n/2个结点.

15、10. 在单链表中设置头指针的作用是：简化操作，减少边界条件的判断11. 在单链表中,除首元结点外,任一结点的存储位置由其直接前驱的指针域 指示.12. 对于一个具有n个结点的单链表,在已知p所指向结点后插入一个新结点的时间复杂度是0(1)_,在值域为给定值的结点后插入一个新结点的时间复杂度为 O(n).13. 在双链表中，每个结点有两个指针域，一个指向_前驱结点 ，另一个指向，后继结点o14. 根据线性表的链式存储结构中每一结点包含的指针个数,将线性表分成单链表和多重链表.15. 在非空双向链表中，在结点q的前面插入结点p的过程如下，请补充p->prior=q->prior;q-

16、>prior- >n ext=p;p->n ext=q;q_>prior=p;16. 一般情况下,将递归算法转换成等价的非递归算法应该设置栈.17. 在解决计算机主机与打印机速度不匹配问题时,通常设置一个打印数据缓冲区，该缓冲区通常是一个 数据结构.18. 循环队列的引入，目的是为了克服假溢出 现象.19. 在栈顶指针为HS的链栈中，判断栈空的条件是 HS=NULL .20. 在具有n个单元的循环队列中,如果不专门设置队满标志,则队满时共n-1有个元素.21. 实现字符串拷贝的函数如下，请补足Void strcpy(char *s, char *t) while(*s+

17、=*t+)!='O')；22. 空格串是由一个或多个空格字符组成的串，其长度等于 其包含的空格个数。23. 空串是 不包含任何字符的串,其长度为0 .24. 设 s='LAM A STUDENT',其长度为:14 .25. 组成串的元素只能是：字符.26. 设 s仁'Good', s2=' : s3='bye!',则 s1,s2和 s3连接的结果是 Good bye!27. 若广义表中每个兀素都是原子时，广义表便成为线性表.28. 广义表的表尾是指除第一个元素外，剩余元素组成的表.29. 广义表A=(a,b,c,d)的表头

18、为(a,b,c,d)表尾为 a .30. 数组的存储结构采用顺序存储方式.31. 设二维数组a0.5, 0.6,其每个字节占5个字节，第一个元素的存储地址为1000,若按列存储，则元素a5,5存储地址为1175 .32. 高度为k的完全二叉树至少有 兰个叶子结点.33. 若一棵二叉树有50个叶子结点，则该二叉树的总结点数至少是_99.34. 有n个叶子结点的哈夫曼树的结点总数为2n-1一35. 根据二叉树的定义，具有三个结点的二叉树有4种.36. 某棵二叉树的中序遍历序列为abcdefg,后序遍历序列为bdcafge,则该二叉树的前序遍历序列eacbdgf ,该二叉树对应的森林包含 2棵二叉树

19、.37. 若二叉树采用二叉链表存储结构，要交换其所有分支结点的左，右子树的位置，利用 遍历方法最为合适.38. 线索二叉树的左线索指向其前驱,右线索指向其 后继.39. 树所对应的二叉树其根结点的右子树一定为空.40. 利用树的孩子兄弟表示法存储，可以将一棵树转化成二叉树.41. 设无向图的顶点个数为n,则该图最多有 n(n-1)/2条边.42. n个顶点的连通图至少有n-1 条边.43. 已知一个图用领接矩阵表示,计算第i个结点的入度的方法是求第i列非零元素的和 .44. G是一个非连通的无向图,共有28条边，则该图至少有 9个顶点.45. 一个图的 邻接矩阵 表示法是唯一的，而邻接表 表示

20、法是不唯一的。0 1 046. 从邻接矩阵A= 1 0 1可以看出,该图共有 3 个顶点,如果是无向图，贝U共有条边.】0 1 0 一47. n个顶点的连通图用邻接矩阵表示时，则该矩阵至少有 2(n-1)个顶点.48. 设图中有n个顶点,e条边,如果用邻接表表示图,进行深度优先搜索遍历的时间复杂度为0(n+e),如果用邻接矩阵表示图,时间复杂度为0( n2)49. 从平均时间性能而言，快速排序排序最佳.50. 堆排序是一种 选择 排序,堆实质上是 一棵完全二叉树 结点的层次序列.对于含有n个元素的排序,堆排序的时间复杂度为 0( I。2®).所需附加的存储结点是 0(1).三、用图表

21、回答下列问题1.设某通信系统使用 A, B , C, D, E, F, G, H个字符，出现的频率 w= 5,29,7,8,14,23,3,11,试构造对应的哈夫曼树(请按左子树根结点的权小于右子树树根结点的权的次序构造)？答案如图：100294219723112915142. 根据下面的邻接链表，画出相应的图，写出每个顶点的度，并用邻接矩阵表示i图丿V1V2V3V4V5V6v1v2v3、：v4Av5v6A* v432324|v2 | ° v5 I v4 |A Iv3p6V6yy"-v3v5-0101100010000000010000000011010000003.画出下

22、列树对应的二叉树，并写出其先根遍历序列：先根遍历序列： A B D E G F C答案如图所示：4. 画出和下列二叉树对应的森林:C四、阅读下列算法，按要求做答1. 下面是删除单链表L中最大元素所在结点的类C语言算法，请补足缺失部分使其完整 void DelMax(Li nkList L) r=L; p=L->n ext;if(P)m=p->data;(1); p=p->n ext;while(p)(3)m=p->data;(4)p=p->n ext;q=r- >n ext; (5); free(q);答案： L->next=NULL ; (2)p!=

23、NULL; (3)q!=NULL ; p->next=r->next(5) r->n ext=p.2. 阅读下列算法，说明该算法的作用Status algorithm1(Li nkQueue & Q)SqStack Stack;QElemType Eleme nt;In itStack(Stack); while(!QueueEmpty(Q) DeQueue(Q,Eleme nt); Push(Stack,Eleme nt); while(!StackEmpty(Stack) Pop(Stack,Eleme nt); En Queue(Q,Eleme nt);答：利用

24、栈实现队列的逆置3. 阅读下列算法，说明该算法的作用Status algorithm2(Stack S, i nt e)Stack T;int d;In itStack(T); while(!StackEmpty(S) Pop(S,d); if(d!=e) Push(T,d); while(!StackEmpty(T) Pop(T,d); Push(S,d);答：利用辅助栈T,将栈S中的元素e删除.4. 将下面程序改写成递归过程void algorithm3(i nt n) int i=n; while(i>1) prin tf(i-);答：void algorithm4(i nt j)

25、 if(j>1) prin tf(j); algorithm4(j-1)5. 阅读下列算法，说明该算法的作用BiTree algorithm5(ElemType Pre, ElemType In )int PreLe n, InLen;int i, j;BiTree BT;ElemType *subPre, *sub In;PreLe n = strle n( Pre);InLen = strle n(l n);if (PreLe n != In Len | PreLen = 0) return NULL;for (i=0; i<I nLen && In i!=Pr

26、e0; i+);if (i = InLen) return NULL;BT = (BiTNode *) malloc(sizeof(BiTNode);BT->data = Pre0;subPre = (ElemType *) malloc(i+1)*sizeof(ElemType); sub In = (ElemType *) malloc(i+1)*sizeof(ElemType); for (j=0; j<i; j+)subPrej = Prej+1; subI nj = In j;subPrej = '0' subl nj = '0'BT-&g

27、t;lchild = CreatBT(subPre, subl n);subPre = (ElemType *) malloc(PreLe n-i)*sizeof(ElemType); sub In = (ElemType *) malloc(PreLe n-i)*sizeof(ElemType); for (j=i+1; j<PreLe n; j+)subPrej-i-1 = Prej;subI nj-i-1 = Inj;subPrej-i-1 = '0' subI nj-i-1 = '0'BT->rchild = CreatBT(subPre, subI n);return BT;答：利用一棵二叉树的先序遍历和中序遍历还原该二叉树五、算法设计题要求插入后保持该表的有序性1. 设顺序表L中的数据元素递增有序.试写一个算法，将e插入顺序表中, void In sertElem(SqList &L, ElemType)j=L.le ngth-1;while(L.elemj>e)L.ele