数据结构考试题

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

2、限集合， R 是 D 上的 D有限集合。 A算法数据元素数据操作数据对象 A操作映象存储关系7.线性表的顺序存储构造是一种A的存储构造 ,线性表的链式存储构造是一种的B存储构造。A随机存取顺序存取索引存取散列存取专业资料整理WORD格式8. 线性表的逻辑顺序与存储顺序总是一致的，这种说法 _B _。A. 正确B. 不正确9. 下面那一条是顺序存储构造的优点 " (A)A . 存储密度大B. 插入运算方便C. 删除运算方便D. 可以方便的用于各种逻辑构造的存储表示10. 线性表采用链式存储构造时, 要求内存中可用的存储单元的地址.A . 必须是连续的B. 局部地址必须是连续的C. 一定

3、不连续D. 连续和不连续都可以11. 表长为 n 的顺序存储的线性表 , 当在任何位置上插入和删除一个元素的概率相等时, 插入一个元素所需要移动元素的平均次数为E, 删除一个元素所需要移动元素的平均次数为AA. (n-1)/2B.nC. n+1D. n-1E. n/2F. (n+1)/2G. (n-2)/212. 带头结点的单链表 head为空的判定条件是 _B_。A. head= =NULLB. head->next= =NULLC. head->next= =headD. head!=NULL专业资料整理WORD格式13. 在一个单链表中 , 假设删除A. p->next

4、= p->next->next C. p= p->next->nextp 所指向结点的后继结点 , 那么执行 _A_。B. p=p->next; p->next= p->next->nextD. p= p->next专业资料整理WORD格式14. 假设一个栈的入栈序列是 1， 2， 3， n，其输出序列为 p1，p2， p3， pn，假设 p1=n，那么 pi 为_C_。A. iB. n=iC. n-i+1D. 不确定专业资料整理WORD格式15.设栈的输入次序为 : 1 , 2,3,4,5,那么不可能是其出栈序列 .A. 54321 B.

5、 45321C. 43512D. 1234516.一个递归算法必须包括BA. 递归局部B. 终止条件和递归局部C. 迭代局部D. 终止条件和迭代局部17.用方式存储的队列 ,在进展删除操作时DA 仅修改头指针B.仅修改尾指针C. 头尾指针都要修改D.头尾指针可能都要修改18. 数组 Am 存放循环队列的元素 , 其头尾指针分别是 front 和 rear, 那么当前队列的元素个数是 _A_。A. (rear-front+m)%mB. (front-rear+m)%mC. front-rear+1D. rear-front+119. 栈和队列的共同特点 _C_。专业资料整理WORD格式A. 都是

6、先进先出C. 允许在端点插入和删除元素B. 都是先进后出D. 没有共同点专业资料整理WORD格式20. 一个栈的入栈序列 a，b，c，d，e，那么栈的输出序列是 _A_。A. edcbaB. decbaC. dceabD. abcde21. 栈的特点是 _B_，队列的特点是 _A_。A. 先进先出B. 先进后出22. 从一个栈顶指针 HS 的链表中删除一个结点 , 用 x 保存被删除的结点值 ,执行的语句为 _C_。A. x=HS; HS=HS->nextB. HS=HS->next; x=HS->data专业资料整理WORD格式C. x=HS->data; HS=HS

7、->nextD. HS->next=HS; x=HS->data23. 在链队列 Q 中 , 插入 s 所指向的结点执行的语句为 _C_。A. Q.front->next=s;B. Q.rear->next=s; Q.rear=sC. s->next=Q.rear;Q.rear=sD. s->next=Q.front;Q.front=s24. 空串与空格串是一样的，这种说法 _B_。A. 正确B. 不正确25. 下面关于串的表达 , 哪一个是不正确的 _B_。A. 串是字符的有限序列B. 空串是由空格构成的串C. 匹配模式是串的一种重要运算D. 串可以

8、采用链式存储构造26. 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作 _B_。专业资料整理WORD格式A. 连接C. 求子串B. 模式匹配D. 求串长专业资料整理WORD格式27.假设串 s='software', 其子串的数目为BA. 8B. 37C. 36D. 928. 二维数组 A 中，每个元素 A 的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA 开场连续存放在存储器内，该数组按行存放时，数组元素 A74 的起始地址为 _C_。A. SA+141B. SA+144C. SA+222D. SA+22529.

9、 对稀疏矩阵进展压缩存储的目的是 _C_.A. 便于进展矩阵运算B. 便于输入输出专业资料整理WORD格式C 节省存储空间D. 降低运算的时间复杂度30. 在以下表达中正确的选项是BA. 线性表的线性存储构造优于链表存储构造B. 二维数组可以看成是其数据元素为线性表的线性表C. 栈的操作方式是先进先出D. 队列的操作方式是先进后出31.广义表 (a),a)的表头为C,表尾为C.A. ()B. aC. (a)D. (a)32.广义表 L=(x,y,z),a,(u,t,w), 从 L 中取出原子项 t 的运算为 _D_。A. Head(Tail(Tail(L)B. Tail(Head(Head(T

10、ail(L)C. Head(Tail(Head(Tail(L)D. Head(Tail(Head(Tail(Tail(L)33.树最适合用来表示BA. 有序的数据元素B. 数据之间具有分支层次关系的数据C. 无序的数据元素D. 无太多关系的数据元素34. 如果某二叉树的前根次序遍历结果为 stuwv，中序遍历为 uwtvs，那么该二叉树的后序为 _B_。A. uwvtsB. vwutsC. wuvtsD. wutsv35. 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是 dgbaechf，那么其后序遍历的结点访问顺序是 _D_。A. bdgcefhaB. gdbe

11、cfhaC. bdgaechfD. gdbehfca专业资料整理WORD格式36. 在一非空二叉树的中序遍历序列中，根结点的右边_A_。专业资料整理WORD格式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. 1039. 由权 (8,2,5,7)的四个叶子结点

12、构造一棵哈夫曼树 , 该树的带权路径长度为 DA. 23B. 37C. 46D. 4340. 利用二叉链表存储树 , 那么根结点的右指针是CA. 指向最左孩子B. 指向最右孩子C. 空D. 非空41. 以下存储方式中 , 哪一个不是树的存储形式 "DA.双亲表示法B. 孩子链表表示法C. 孩子兄弟表示法D. 顺序存储表示法42.在一个无向图中，所有顶点的度数之和等于所有边数的_C_倍。A. 1/2B. 1C. 2D. 443.具有 n 个顶点和多于 n-1 条边的无向图B .A.有可能是树B. 一定不是树C. 一定是树D. 以上答案都不对专业资料整理WORD格式44. 具有 6 个顶

13、点的无向图至少应有_A_条边才能确保是一个连通图。专业资料整理WORD格式A. 5B. 6C. 7D. 8专业资料整理WORD格式45. 无向图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专业资料整理WORD格式A. abecdfB. acfebdC. aebcfdD. aedfcb专业资料整理WORD格式46. 下述几种排序方法中，要求内存量最大的是 _D_。A. 插入排序B. 选择排序C. 快速排序D. 归并排序47. 排序方法中，从未排序序

14、列中依次取出元素与已排序序列初始时为空中的元素进展比拟，将其放入已排序序列的正确位置上的方法，称为 _C_。A. 希尔排序B. 起泡排序C. 插入排序D. 选择排序48. 在待排序的元素序列根本有序的前提下，效率最高的排序方法是_A_。A.插入排序B. 选择排序C. 快速排序D. 归并排序49. 以下排序算法中 , 哪一个是稳定的排序算法 "BA. 直接选择排序B. 二分法插入排序C. 希尔排序D. 快速排序50. 将两个各有 n 个元素的有序表归并成一个有序表 , 其最少的比拟次数AA. nB. 2n-1C. 2nD. n-1二、填空题1. 算法的五个重要特性是有穷性 ,确定性 ,

15、可行性 ,输入和输出 .2. 数据的树型构造和图 (网)状构造合称非线性构造.3.抽象数据类型的定义仅取决于它的一组逻辑特性 , 而与数据在计算机中的表示和实现无关 .4.评价算法质量的指标是 正确性 ,易读性 ,强健性 ,高效性 .专业资料整理WORD格式5. 数据构造中评价算法的两个重要指标是 : 时间复杂度和空间复杂度 .6.分析下面算法程序段，的时间复杂度是 _ O (mn)_。s=0;for (i=0;i<n;i+)for (j=0;j<m;j+)s+=Bij;7. 当线性表元素的总数根本稳定 , 且很少进展删除和插入操作时 , 但是要求以最快的速度存取线性表中的元素 ,

16、 应该采取 顺序 存储构造 .8.顺序表中逻辑上相邻的元素的物理位置必定 相邻 , 而单链表中逻辑上相邻的元素的物理位置不一定 相邻 .9.在各个结点查找概率相等的情况下 , 从 n 个结点的单链表中查找一个结点 , 平均要访问 n/2个结点 .10. 在单链表中设置头指针的作用是 : 简化操作 , 减少边界条件的判断 .11. 在单链表中 , 除首元结点外 , 任一结点的存储位置由其直接前驱的指针域 指示 .12.对于一个具有 n 个结点的单链表 , 在 p 所指向结点后插入一个新结点的时间复杂度是O(1), 在值域为给定值的结点后插入一个新结点的时间复杂度为 O(n).13.在双链表中，每

17、个结点有两个指针域，一个指向_前驱结点 _，另一个指向 _后继结点 _ _。14. 根据线性表的链式存储构造中每一结点包含的指针个数 , 将线性表分成 单链表 和 多重链表 .15. 在非空双向链表中 , 在结点 q 的前面插入结点 p 的过程如下 , 请补充p->prior=q->prior;q->prior->next=p;p->next=q;q->prior=p;16. 一般情况下 , 将递归算法转换成等价的非递归算法应该设置栈 .17. 在解决计算机主机与打印机速度不匹配问题时 , 通常设置一个打印数据缓冲区 , 该缓冲区通常是一个队列 数据构造.1

18、8. 循环队列的引入 , 目的是为了克制 假溢出 现象 .19.在栈顶指针为 HS 的链栈中 , 判断栈空的条件是HS=NULL .20.在具有 n 个单元的循环队列中 , 如果不专门设置队满标志 , 那么队满时共n-1 有个元素 .专业资料整理WORD格式21. 实现字符串拷贝的函数如下 , 请补足Void strcpy(char *s, char *t)专业资料整理WORD格式 while(*s+=*t+)!='0');专业资料整理WORD格式22. 空格串是 _由一个或多个空格字符组成的串_，其长度等于 _其包含的空格个数。专业资料整理WORD格式23. 空串是 不包含任

19、何字符的串 , 其长度为 0 .24. 设 s='I AM A STUDENT', 其长度为 : 14 .25. 组成串的元素只能是 : 字符 .26. 设 s1='Good', s2=' ', s3='bye!', 那么 s1,s2和 s3 连接的结果是Good bye!27. 假设广义表中每个元素都是原子时 , 广义表便成为 线性表 .28. 广义表的表尾是指除第一个元素外 ,剩余元素组成的表 .29. 广义表 A=(a,b,c,d)的表头为(a,b,c,d) ,表尾为().30. 数组的存储构造采用 顺序 存储方式 .31.

20、设二维数组 a0.5, 0.6, 其每个字节占5 个字节 , 第一个元素的存储地址为1000, 假设按列存储 , 那么元素 a5,5存储地址为 1175 .32.高度为 k 的完全二叉树至少有2k 2个叶子结点 .33. 假设一棵二叉树有 50 个叶子结点 , 那么该二叉树的总结点数至少是 99.34. 有 n 个叶子结点的哈夫曼树的结点总数为2n-1.35. 根据二叉树的定义 , 具有三个结点的二叉树有4 种.36. 某棵二叉树的中序遍历序列为abcdefg, 后序遍历序列为bdcafge, 那么该二叉树的前序遍历序列eacbdgf , 该二叉树对应的森林包含 2 棵二叉树.37. 假设二叉

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

22、顶点 .45.一个图的 邻接矩阵 表示法是唯一的，而邻接表 表示法是不唯一的。01046.从邻接矩阵 A101 可以看出,该图共有3个顶点 ,如果是无向图 , 那么共有2条边 .01047.n 个顶点的连通图用邻接矩阵表示时, 那么该矩阵至少有 2(n-1)个顶点 .48.设图中有 n 个顶点 , e 条边 , 如果用邻接表表示图 ,进展深度优先搜索遍历的时间复杂度为O(n+e) , 如果用邻接矩阵表示图 , 时间复杂度为 O(n2 )49.从平均时间性能而言 ,快速排序排序最正确 .50.堆排序是一种选择排序 , 堆实质上是 一棵完全二叉树结点的层次序列 . 对于含有 n 个元素的排序 ,

23、堆排序的时间复杂度为O( l o2gn) .所需附加的存储结点是O(1) .三、用图表答复以下问题1. 设某通信系统使用 A ，B，C，D， E， F， G，H 个字符，出现的频率 w= ， ，试构造对应的哈夫曼树请按左子树根结点的权小于右子树树根结点的权的次序构造"答案如图 :100425819FB292329DHE1581114C8专业资料整理WORD格式7专业资料整理WORD格式2.根据下面的邻接链表，画出相应的图，写出每个顶点的度, 并用邻接矩阵表示 .专业资料整理WORD格式v1v2v3答案如下图 :v4V1: 3V2: 2v5V3: 3v6V4: 2V5: 4V6: 2v

24、2v5v4v3v5v6v4v6v1v3 v2v3v4v5专业资料整理WORD格式V6专业资料整理WORD格式0101100010000000010000000011010000003. 画出以下树对应的二叉树，并写出其先根遍历序列：ABCDFEG先根遍历序列：ABDEGFC答案如下图 :专业资料整理WORD格式ABDCEGF4. 画出和以下二叉树对应的森林：AAAABBBCCC专业资料整理WORD格式答 :AAABCACBBC四、阅读以下算法，按要求做答.1. 下面是删除单链表 L 中最大元素所在结点的类 C语言算法 , 请补足缺失局部使其完整 . void DelMax(LinkList L

25、)r=L; p=L->next; if(p)专业资料整理WORD格式m=p->data;(1); p=p->next;while(p)if(2)专业资料整理WORD格式(3); m=p->data;(4) ; p=p->next;q=r->next;(5); free(q);答案 : (1) L->next=NULL ; (2)p!=NULL;(3)q!=NULL ; (4) p->next=r->next专业资料整理WORD格式(5) r->next=p.2. 阅读以下算法，说明该算法的作用。Status algorithm1(Li

26、nkQueue &Q) SqStack Stack; QElemType Element;InitStack(Stack);while(!QueueEmpty(Q)DeQueue(Q,Element);Push(Stack,Element);while(!StackEmpty(Stack)Pop(Stack,Element);EnQueue(Q,Element);答 :利用栈实现队列的逆置 .3. 阅读以下算法，说明该算法的作用。Status algorithm2(Stack S, int e) Stack T;int d;专业资料整理WORD格式InitStack(T);专业资料整理

27、WORD格式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(int n)int i=n; while(i>1)printf(i-);答 :void algorithm4(int j)if(j>1)printf(j);algorithm4(j-1)专业资料整理WORD格式5. 阅读以下算法，说明该算法的作用。BiTree algorith

28、m5(ElemType Pre, ElemType In)int PreLen, InLen;int i, j;BiTree BT;ElemType *subPre, *subIn;PreLen = strlen(Pre);InLen = strlen(In);if (PreLen != InLen | PreLen = 0) return NULL;for (i=0; i<InLen && Ini!=Pre0; i+);if (i = InLen) return NULL;BT = (BiTNode *) malloc(sizeof(BiTNode);BT->da

29、ta = Pre0;subPre = (ElemType *) malloc(i+1)*sizeof(ElemType);subIn = (ElemType *) malloc(i+1)*sizeof(ElemType);for (j=0; j<i; j+)subPrej = Prej+1;subInj = Inj;subPrej = '0' subInj = '0'BT->lchild = CreatBT(subPre, subIn);专业资料整理WORD格式subPre = (ElemType *) malloc(PreLen-i)*sizeof

30、(ElemType);subIn = (ElemType *) malloc(PreLen-i)*sizeof(ElemType);for (j=i+1; j<PreLen; j+)subPrej-i-1 = Prej;subInj-i-1 = Inj;subPrej-i-1 = '0' subInj-i-1 = '0'BT->rchild = CreatBT(subPre, subIn);return BT;答 : 利用一棵二叉树的先序遍历和中序遍历复原该二叉树.五、算法设计题1. 设顺序表 L 中的数据元素递增有序 . 试写一个算法 , 将 e 插入顺序表中 , 要求插入后保持该表的有序性 . void InsertElem(SqList