当前位置：文档之家 › 数据结构复习题库

数据结构复习题库

  • 格式：doc
  • 大小：112.50 KB
  • 文档页数：6

一、 填空填 1. 数据结构及数据的逻辑结构包括集合、_________ 、_________、图形结构（网状结构）四种类型。 2. 通常从四个方面评价算法的质量： 、可读性、健壮性和______________________。 3. 一种数据结构的元素集合K和它的二元关系R为K=｛a,b,c,d,e,f,g,h｝，R=｛b>，，，，，，｝，该数据结构具有______结构。 4. 在线性结构和树型结构中，前驱结点和后继结点之间分别存在着一对一和______的联系。 5. 线性表、栈和队列都是_______结构，对于栈只能在_______插入和删除元素；对于队列只能在_______插入元素，在______删除元素。 6. 子串“ABC”在主串“ABABCABCD”中的位置为 ______。 7. 已知广义表A=(((a,b),(c),(d,e))), GetHead(GetTail(GetTail(GetHead(A))))的结果是______。 8. 对于一棵具有n个结点的树，该树中所有结点的度数之和为______。 9. AOV网是一种___________的图。 10. 一棵深度为k的满二叉树的结点总数为______，一棵深度为k的完全二叉树的结点总数的最小值为______。 11. 在一个具有n个顶点的有向完全图中，至多包含有______条边。 12. 使用分块查找时是，除表本身外，尚需建立一个索引表，用来存放每一块中的最大___________及该块的起始地址。 13. 一个好的哈希函数其转换地址应尽可能___________，而且函数运算应尽可能简单。 14. 动态查找表和静态查找表的重要区别在于前者包含有插入和___________运算，而后者不包含这两种运算。 15. 数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和______，并由此得到两种不同的存储结构是顺序存储结构和链式存储结构。 16. 设元素1，2，3，4，5依次进栈，若要在输出端得到序列34251，则应进行的操作序列为push(S,1),push(S,2), ______，pop(S)，push(S,4)，pop(S)，______，______,pop(S)，______。 17. 一个算法应具有_____，确定性，可行性，_____，_____这五个特征。 18. 数据结构及数据的逻辑结构包括______ 、线性结构、树型结构、______四种类型。 19. 通常从四个方面评价算法的质量：正确性、 、__________和效率与低存储量需求。 20. 子串“ABC”在主串“ABDABCABCD”中的位置为______。 21. 一棵深度为k的完全二叉树的结点总数的最小值为______，最大值为______。 22. 如图所示的二叉树的中序遍历序列是__________。

23. 在双向链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向______。 24. 对于一个具有n个结点的二叉树，它可能具有的最小深度为______，具有的最大深度为______。 25. 一个算法的时间复杂性通常用它的数量级形式表示，当一个算法的时间复杂度与问题的规模n大小无关时，则表示为O(1)；成正比时，则表示为O(n)；成平方时，则表示为______ 。

26. 通常从四个方面评价算法的质量： 、可读性、健壮性和__________。 27. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为__________。 28. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树深度为________，树的度为_________。

29. 后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。

30. AOV网是一种___________________的图。 31. 在一个具有n个顶点的无向完全图中，至少包含有________条边；在一个具有n个顶点的有向完全图中，至多包含有_______________条边。

二、选择题 1. 在一个长度为n的顺序表中，删除值为x的元素时需要比较元素和移动元素的总次数为（ ） A. （n+1）/2 B.n/2 C. n D.n+1 2. 下面程序段的时间复杂度的量级为（ ） for(i=1;i<=n;i++) for (j=1;j<=i;j++) for (k=1;k<=j;k++) x=x+1; A. O(1) B. O(n) C. O(n 2) D. O(n3) 3. 如图所示的4棵二叉树中，（ ）不是完全二叉树。 4. 一个栈的入栈序列1，2，3，4，则它的不可能的输出序列是（ ）。 A. 1，2，3，4 B. 4，3，2，1 C. 1，3，4，2 D. 4，1，2，3 5. 在有n个结点的二叉链表中，值为空的链域个数为（ ）。 A. n-1 B. 2n-1 C. n+1 D. 2n+1 6. 已知完全二叉树有30个结点，则整个二叉树有（ ）个度为1的结点。 A. 0 B. 1 C. 2 D. 不确定 7. 假定一个顺序循环队列存储于数组a[N]中，其队首和队尾指针分别用front和rear表示，则判断队列满的条件为（ ） A. （rear-1）%N= =front B. （rear+1）%N= =front C. （front-1）%N= =rear D. （front+1）%N= =rear 8. 设两个字符串的串值分别为s1=“ABCDEFG”，s2=“PQRST”，则Concat(&T,SubString(&T1,s1,2,LenStr(s2)),SubString(&T2,s1,LenStr(s2),2))的结果串是（ ） A．BCDEF B. BCDEFG C. BDPQRST D. BCDEFEF 9. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。 A.2h B.2h-1 C.2h+1 D.h+1

10. 广义表((a,b,c,d))的表头和表尾分别是（ ）。

A. (a,b,c,d)和(a,b,c,d) B. a和d C. (a,b,c,d)和( ) D. a和( ) 11. 一个满二叉树有x个叶子结点，y个分支结点，z个结点，则（ ）。

A. z=y-x B. y+x=2z C. x=y-1 D. z=2y+1 12. 对于长度为256的表，采用分块查找，每块的最佳长度为（ ）。

A. 16 B. 12 C. 6 D. 20 13. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点点数为2个，则度为0的结点数为（ ）个。 A.3 B.4 C.5 D.6 14. 一棵二叉树的先序序列和中序序列相反，则该二叉树一定满足（ ） A. 其中只有一个叶子结点 B. 其中任意结点没有左孩子 C. 其中任意结点没有右孩子 D. b或c 15. 一棵具有80个结点的完全二叉树的深度为（ ） A.6 B.7 C.5 D.8 16. 在数据结构中，从逻辑上可以把数据结构分成（ ） A. 动态结构和静态结构 B.紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D.内部结构和外部结构 17. 下面（ ）的时间复杂性最好，即执行时间最短。 A. O(n) B.O(logn) C. O(nlogn) D.O(n2) 18. 一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时，需要从后面向前依次后移（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 19. 在一棵树中，每个结点最多有（ ）个前驱结点。 A.0 B.1 C.2 D.任意多个 20. 在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（ ）个指针域的值。 A. 1 B. 2 C. 3 D.4 21. 在一个顺序表的表尾插入一个元素的时间复杂度的量级为（ ） A. O(n) B.O(1) C. O(n2) D.O(logn) 22. 在有n个结点的二叉链表中，值为空的链域个数为（ ）。 A. n-1 B. 2n-1 C. n+1 D. 2n+1 23. C语言中，判定一个栈S为空的条件是（ ） A .S. top= =S.base-1 B. S. top= =0 C. S. top= =S.base+1 D .S. top= =S.base 24. 一棵具有35个结点的完全二叉树的深度为（ ） A.6 B.7 C.5 D.8 25. 在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。 A.1/2 B. 1 C. 2 D. 4 26. 一棵左右子树均不空的二叉树在后序线索化后，其中空的链域的个数是（ ） A.不确定 B.0 C.1 D.2

27. 栈和队列的共同特点是（ ）。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点

28. 用链接方式存储的队列，在进行插入运算时（ ）。 A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改

29. 以下数据结构中哪一个是非线性结构？（ ） A. 队列 B. 栈 C. 线性表 D. 二叉树 30. 树最适合用来表示（ ）。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据

31. 二叉树的第k层的结点数最多为（ ）。 A．2k+1 B.2K+1 C.2K-1 D. 2k-1 32. 设某无向图具有n个顶点e条边，则该无向图中所有顶点的度数之和为（ ）。

合集下载

数据结构复习试题

数据结构复习试题

题目选至第7章一、填空题（2分/题，共10题）1．数据是指所有能够输入到计算机中被计算机加工、处理的符号的集合。

2．可以把计算机处理的数据，笼统地分成数值型和非数值型两大类。

3．数据的逻辑结构就是指数据间的邻接关系。

10．从整体上看，数据在存储器有两种存放的方式：一是集中存放在一个连续的存存储区中；一是利用存储器中的零星区域，分散地存放在存的各个地方。

12．“基本操作”是指算法中那种所需时间与操作数的具体取值无关的操作。

5．不带表头结点的链表，是指该链表的表头指针直接指向该链表的起始结点。

6．在一个双链表中，已经由指针ptr指向需要删除的存储结点，则删除该结点所要执行的两条操作是①ptr->Prior->Next = ptr->Next; ②ptr->Next->Prior = ptr->Prior; 。

7．设tail是指向非空、带表头结点的循环单链表的表尾指针。

那么，该链表起始结点的存储位置应该表示成 tail->Next->Next 。

9．顺序表Sq = (a1，a2，a3，…，an)（n≥1）中，每个数据元素需要占用w个存储单元。

若m为元素a1的起始地址，那么元素an的存储地址是 m+(n-1)*w 。

1．限定插入和删除操作只能在一端进行的线性表，被称为是栈。

2．如果在顺序栈满时仍打算进行进栈操作，就称为发生了“上溢”出错。

3．如果在顺序栈空时仍打算进行出栈操作，就称为发生了“下溢”出错。

4．在具有n个数据结点的循环队列中，队满时共有 n-1 个数据元素。

5．如果操作顺序是先让字母A、B、C进栈，做两次出栈；再让字母D、E、F进栈，做一次出栈；最后让字母G进栈，做三次出栈。

最终这个堆栈从栈顶到栈底的余留元素应该是 DA 。

6．中缀表达式(a+b)-(c/(d+e))对应的后缀表达式是 ab+cde+/- 。

7．函数的递归调用有两种形式：如果一个函数是直接调用自己，就称其为直接递归调用；如果一个函数是通过另一个函数来调用自己，就称其为间接递归调用。

数据结构复习题

数据结构复习题

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×）第1章（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。

（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。

（×）（3）数据元素是数据的最小单位。

（×）（4）数据项是数据的基本单位。

（×）（5）数据的逻辑结构和数据的存储结构是相同的。

（√）（6）数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。

（√）（7）数据的物理结构是指数据在计算机内实际的存储形式。

（√）（8）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（√）（9）数据的存储结构是数据的逻辑结构的存储映像。

（√）（10）算法是对解题方法和步骤的描述。

第2章（×）（1）链表的物理存储结构具有同链表一样的顺序。

（×）（2）链表的每个结点都恰好包含一个指针域。

（√）（3）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。

（×）（4）链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

（×）（5）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

（√）（6）数组元素的存储位置是下标的线性函数。

（√）（7）在单链表中，元素的存储位置用指针联系，所以可以从头结点开始查找任何一个元素。

（×）（8）顺序存储线性表的插入和删除操作不需要付出很大的代价，因为平均每次移动仅一半的元素。

（×）（9）顺序存储方式的优点是存储密度大，插入、删除效率高。

（×）（10）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。

第3章（√）（1）大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。

数据结构复习题及答案

数据结构复习题及答案

中南大学现代远程教育课程考试（考试）复习题及参考答案数据结构(使用教材：余腊生编著，人民邮电出版社出版，《数据结构—基于C++模板类的实现》一、判断题1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

[ ] 2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。

[ ]3．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

[ ] 4．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。

[ ] 5．一个广义表的表尾总是一个广义表。

[ ] 6．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。

[ ] 7．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。

[ ] 8．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。

[ ] 9．直接选择排序是一种稳定的排序方法。

[ ] 10．30、闭散列法通常比开散列法时间效率更高。

[ ] 11．有n个结点的不同的二叉树有n!棵。

[ ] 12．直接选择排序是一种不稳定的排序方法。

[ ] 13．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。

[ ] 14．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。

[ ] 15．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。

[ ] 16．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。

在设计再散列函数时，要求计算出的值与表的大小m互质。

[ ] 17．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

[ ] 18．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。

数据结构期末复习题

数据结构期末复习题

数据结构期末复习题习题⼀绪论习题答案1.1 1. AB2. BD3. C4. AB5. CA6. CB7. B8. D9. B 10. B1.2 1. 线性结构、树形结构、图形结构、⾮线性结构2. 没有、1、没有、13. 前驱、1、后续、任意多个4. 任意多个5. ⼀对⼀、⼀对多、多对多6. 有穷性、确定性、可⾏性、输⼊、输出7. O（m*n）8. O (n 1 2)9. O (n2)10. log3n1.1 单项选择题1. 数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。

①A．操作对象Ｂ．计算⽅法Ｃ．逻辑存储Ｄ．数据映象②A．结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②有限集合。

①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．逻辑结构②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成①。

A．动态结构和静态结构Ｂ．紧凑结构和⾮紧凑结构Ｃ．线性结构和⾮线性结构Ｄ．内部结构和外部结构4. 线性表的顺序存储结构是⼀种①的存储结构，线性表的链式存储结构是⼀种②的存储结构。

A．随机存取B．顺序存取C．索引存取D．散列存取5. 算法分析的⽬的是①，算法分析的两个主要⽅⾯是②。

① A. 找出数据结构的合理性 B. 研究算法中的输⼊和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和⽂档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和⽂档性D. 数据复杂性和程序复杂性6. 计算机算法指的是①，它必具备输⼊、输出和②等五个特性。

①A. 计算⽅法 B. 排序⽅法C. 解决问题的有限运算序列D. 调度⽅法②A. 可⾏性、可移植性和可扩充性 B. 可⾏性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性7. 线性表的逻辑顺序与存储顺序总是⼀致的，这种说法①。