武大数据结构试题

⑴ 数据结构本科试题

6 、A （至多有2^(k-1)个节点。k为深度）
7、A（简单排一下，就发现父节点就是编号/2）
8、B（队列先进先出）
9、B（
结点的权：在一些应用中，赋予树中结点的一个 有某种意义的实数。
结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
树的带权路径长度：为树中所有叶结点的带权路径长度之和）
10、B（先访问根节点、再访问左子树，最后右子树）
11、C（首先肯定是线性结构，排除D，其次，队列和栈，顺序存储、链式存储皆可。A、B显然不对）

⑵ 求下面数据结构试题的答案...

一．

1,复杂性2.线性结构非线性结构

3．可以按序号随机存取4.数据元素

5.后进先出6.n7.只能在队头进行

9.长度1深度1

10-+A*BC/DE

11

12顶点Vp到顶点Vq之间的路径是指定的序列Vp，Vi1，Vi2•••Vim，Vq。

13n（n-2）/214n—1152n—1

17一种存储结构

19可以从表中任意结点开始遍历整个链表；只用一个指向尾结点的指针对链表头、尾进行操作，提高了效率。

20栈是仅限制在表的一端进行插入和删除的运算的线性表，是一种操作受限的线性表。

二．

1算法的时间复杂度和空间复杂度

2.队列

3.

4嵌套集合表示法，广义表表示法，凹入表示法

5.456.S(1)X(1)S(2)S(3)X(3)S(4)X(4)X(2)

7（1）O（nˆ2）

（2）O（nˆ2）

8.

哈夫曼树：

WPL=2*5+4*5+5*4+16*3+8*3+7*3+30=173

9.邻接矩阵：

邻接表：

10.二叉树：

前序：ABCEFD

中序：BEFCDA

后序：FEDCBA

⑶ 数据结构 试题 求答案

首先，定义一个数组存放上表所有数据（共46个数据）。设这个数组为A(46)
然后按下列步骤进行排序计算
1）A(1)≤A(2)？是转第2步，否则

A(1)<-->A(2)（即A(1)、A(2)值互换，实现A(1)≤A(2)）
2）A(2)≤A(3)？是（说明A(1)≤A(2)≤A(3)）转第3步，否则

A(2)<-->A(3)（实现A(2)≤A(3)）

A(1)≤A(2)？是（说明A(1)≤A(2)≤A(3)）转第3步，否则

A(1)<-->A(2)（实现A(1)≤A(2)≤A(3)）
3）A(3)≤A(4)？是（说明A(1)≤A(2)≤A(3)≤A(4)）转第4步，否则

A(3)<-->A(4)（实现A(3)≤A(4)）

A(3)≥A(2)？是（说明A(1)≤A(2)≤A(3)≤A(4)）转第4步，否则

A(2)<-->A(3)（实现A(2)≤A(3)）

A(2)≥A(1)？是（说明A(1)≤A(2)≤A(3)≤A(4)）转第4步，否则

A(1)<-->A(2)（实现A(1)≤A(2)≤A(3)≤A(4)）
4）A(4)≤A(5)？是（说明A(1)≤A(2)≤A(3)≤A(4)≤A(5)）转第5步，否则

A(4)<-->A(5)（实现A(4)≤A(5)）

A(4)≥A(3)？是（说明A(1)≤A(2)≤A(3)≤A(4)≤A(5)）转第5步，否则

A(3)<-->A(4)（实现A(3)≤A(4)）

A(3)≥A(4)？是（说明A(1)≤A(2)≤A(3)≤A(4)≤A(5)）转第5步，否则

A(2)<-->A(3)（实现A(2)≤A(3)）

A(2)≥A(1)？是（说明A(1)≤A(2)≤A(3)≤A(4)≤A(5)）转第5步，否则

A(1)<-->A(2)（实现A(1)≤A(2)≤A(3)≤A(4)≤A(5)）
5）A(5)≤A(6)？是转第6步，否则

A(5)<-->A(6)

A(5)≥A(4)？是转第6步，否则

A(4)<-->A(5)

A(4)≥A(3)？是转第6步，否则

A(3)<-->A(4)

A(3)≥A(2)？是转第6步，否则

A(2)<-->A(3)

A(2)≥A(1)？是转第6步，否则

A(1)<-->A(2)
6）......

按如上思路进行下去，即可实现A(46)数组按升序重排。

由上述1）~5）步的比较过程可以看出，每执行一步，就完成一次若干组数据从小到大的排序，且执行比较时，总是从已排好序的最大那个数开始，从大到小进行边比较边调整次序。另一个特点是，越到后面，每一步中需要比较与调整的数据越多。

⑷ 数据结构概论 试题求解

二、判断对错题：（每题2分，共40分，正确的选A，错误的选B）
1. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。B
2. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。B
3. 取线性表的第i个元素的时间同i的大小有关。B
4. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。A
5. 二叉树是一般树的特殊情形。B
6. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。B
7. 在n个结点的无向图中，若边数大于n-1,则该图必是连通图。B
8. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。B(折半最小）
9. Hash表的平均查找长度与处理冲突的方法无关。B
10. 用邻接矩阵表示图时，矩阵元素的个数与边的条数有关.A
11. 树最适合用来表示元素之间具有分支层次关系的数据。A
12. 图型结构中元素之间存在1对多关系。A
13. 哈夫曼树度为1的结点数等于度为2和0的结点数之差。
14. 两个串相等的充分必要条件是分配的存储空间一样。B
15. 已知指针P指向键表L的某结点，执行语句P=P->next不会删除该链表中的结点。A
16. 在链队列中，即使不设置尾指针也能进行入队操作。A
17. 若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。A
18. 直接选择排序算法在最好情况下的时间复杂度为O（N），N是数据元素的个数。B
19. 排序算法中的比较次数与初始元素序列的排列无关。B
20. 记录是数据处理的最小单位。B
21. 程序一定是算法。B
22. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。A
23. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.B
24. 循环链表不是线性表.B
25. 顺序存储结构通过数据元素存储的位置表示元素之间的关系。A
26. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。B
27. 循环队列的引入，目的是为了克服假溢出。A
28. 完全二叉树一定存在度为1的结点B。
29. 对一棵二叉树进行层次遍历时，应借助于一个栈。B
30. 二叉树只能用二叉链表表示。B
31. 树中的结点和图中的顶点就是指数据结构中的数据元素。A
32. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。B
33. 带权的有向图和无向图，只能使用邻接表存储形式来存储它。B
34. 适用于折半查找的表的存储方式及元素排列要求是：链接方式存储，元素无序 。B
35. 当采用分快查找时，数据的组织方式为数据分成若干块，每块内数据有序。B
36. 散列函数越复杂越好，因为这样随机性好，冲突概率小。B
37. 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法。A
38. 在排序过程中，主要进行的两种基本操作是关键字的比较和记录的移动。A
39. 链表中的头结点仅起到标识的作用。B
40. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以结点移动量为标准分析。A
41. 为了很方便的插入和删除数据，可以使用双向链表存放数据。A
42. 栈是实现过程和函数等子程序所必需的结构。A
43. 在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为模式串的最末字符。A
44. 在单链表中，指针p指向元素为x的结点，实现"删除x的后继"的语句是p->next=p->next->next;B
45. 完全二叉树一定存在度为1的结点。B
46. 连通图上各边权值均不相同，则该图的最小生成树是唯一的。A
47. 通常将链串的结点大小设置为大于1是为了提高存储密度。
48. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。B
49. 快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。B
50. 邻接多重表是无向图和有向图的链式存储结构。B
51. 强连通图的各顶点间均可达。A
52. 度为二的树就是二叉树。B
大概都对吧，个别没确定答案，自己判断了下