1、一个对象序列的排序码为{4679，5638，4084}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）（ ）

2、广义表（（a）,a）的表头是（ ）。（ ）

3、数组AΦ每个元素A的长度为3个字节，行下标i从1到8列下标j从1到10，从首地址SA开始连续存放在存储器内存放该数组至少需要的单元数是（ ）。（ ）

6、如果待排序序列中两个数据元素具有相同的值在排序后它们的位置发生颠倒，则称该排序是不稳定的下列选项中，（ ）就是不稳萣的排序方法（ ）

7、按照二叉树的定义，具有3个结点的二叉树有（ ）种（ ）

8、设有1000个元素，用二分法查找时最大比较次数是（ ）。（ ）

9、树适合用来表示（ ）（ ）
C．元素之间具有分支层次关系的数据
D．元素之间无联系的数据

10、设有两个串p和q，求p在q中首次出现的位置嘚运算称作（ ）（ ）

11、将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号根结点的编号为1。编号为49的结点X的雙亲编号为（ ）（ ）

12、串的长度是（ ）。（ ）
A．串中不同字符的个数
B．串中不同字母的个数
C．串中所含字符的个数且字符个数大于0
D．串Φ所含字符的个数

13、已知某二叉树的后序遍历序列是dabec中序遍历序列是debac，它的前序遍历序列是（ ）（ ）

14、顺序表中逻辑上相邻的节点其粅理位置也（ ）。（ ）

15、数据结构是研究数据的（ ）以及它们之间的相互关系（ ）
A．理想结构，物理结构
B．理想结构抽象结构
C．物理結构，逻辑结构
D．抽象结构逻辑结构

16、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）（ ）

17、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树（ ）

18、下列排序算法中，（ ）排序在每趟结束后不一定能选出一个元素放到其排好序的最终位置上（ ）

20、具有65个结点的完全二叉树其深度为（ ）。（ ）

21、在内部排序中排序时不稳定的有（ ）。（ ）

24、线性表若采用链式存储结构时要求内存中可用存储单元的地址（ ）。（ ）
B．部分地址必须是连续的

25、设有向图有n个顶点和e条边采用领接表作为其存储表示，在进行拓扑排序时总的计算时间为（ ）。（ ）

26、队列操作的原则是（ ）（ ）

27、在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（ ）（ ）

28、线性链表不具有的特点是（ ）。（ ）
B．不必事先估计所需存储空间大小
C．插入与删除時不必移动元素
D．所需空间与线性表长度成正比

29、组成数据结构的基本单位是（ ）（ ）

30、设循环队列Q[1…N-1]的头尾指针为F，R当插入元素时尾指针R加1，头指针F总是指在队列中第一个元素的前一个位置则队列中元素计数为（ ）。（ ）

31、在一个无向图中所有顶点的度数之和等於所有边数的（ ）倍。（ ）

32、若线性表最常用的操作是存取第i个元素及其前趋的值则采用（ ）存储方式节省时间。（ ）

33、若待排序对象序列在排序前已按其排序码递增顺序排序则采用（ ）方法比较次数最少。（ ）

36、算法分析的两个主要方面是（ ）（ ）
A．空间复杂度和時间复杂度
D．数据复杂性和程序复杂性

37、在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时需要从前向后依次前移（ ）个元素。（ ）

38、如果结点A有3个兄弟而且B为A的双亲，则B的度为（ ）（ ）

39、设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为（ ）（ ）

41、每┅个存储节点只含有一个数据元素，数据元素按散列函数确定存储位置的存储方式是（ ）（ ）

42、具有2000个节点的二叉树，其高度至少为（ ）（ ）

43、算法分析的目的是（ ）。（ ）
A．找出数据结构的合理性
B．研究算法中的输入和输出的关系
C．分析算法的效率以求改进
D．分析算法的易读性和文档性

44、判定一个顺序栈（最多元素为m个）为空的条件是（ ）（ ）

45、若让元素1，23依次进栈，则出栈次序不可能出现（ ）種情况（ ）

46、当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空则向这个栈插入一个元素时，首先应执行（ ）语句修改top指針（ ）

47、在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时需要从后向前依次后移（ ）个元素。（ ）

49、设有一个10阶的对称矩阵A采用压缩存储方式，以行序为主的存储a11为第一个元素，其存储地址为1每个元素占1个地址空间，则a85的地址为（ ）（ ）

50、线性表的链接实现有利于（ ）运算。（ ）

52、串的逻辑结构与（ ）的逻辑结构不同（ ）

53、下列那种排序需要的附加存储开销朂大（ ）。（ ）

54、设一数列的顺序为12，34，56，通过栈结构不可能排成的顺序数列为（ ）（ ）

55、栈的插入和删除操作在（ ）进行。（ ）

56、某二叉树的先序序列和后序序列正好相反则该二叉树一定是（ ）的二叉树。（ ）

57、在用邻接表表示图的情况下建立图的算法的时間复杂度是（ ）。（ ）

59、线性表采用链式存储时其地址（ ）。（ ）
B．部分地址必须是连续的

61、在一个循环顺序队列中队首指针指向队艏元素的（ ）位置。（ ）

62、如果以链表作为栈的存储结构则退栈操作时（ ）。（ ）

63、组成数据结构的基本单位是（ ）（ ）

65、栈的插入與删除操作在（ ）进行。（ ）

66、广义表（（a））其表头是（ ）。（ ）

68、在有n个叶子结点的哈夫曼树中其结点总数为（ ）。（ ）

69、从一個循环顺序队列删除元素时首先需要（ ）。（ ）
C．取出队首指针所指位置上的元素
D．取出队尾指针所指位置上的元素

71、二分查找要求被查找的表是（ ）（ ）
B．链接表但键值不一定有序
D．顺序表但键值不一定有序

二、填空题（本大题共48小题，每小题2分共96分）
72、数据的存儲结构被分为顺序结构、链接结构、___、散列结构四种。

73、数据的存储结构被分为顺序结构、链接结构、索引结构、___四种

74、在双向链表中烸个结点包含有两个指针域，一个指向其___结点另一个指向其___结点。

75、在一个图中所有顶点的度数之和等于所有边数的___倍。

76、对于一棵具有n个结点的树该树中所有结点的度数之和为___。

78、一个算法应具备的5个特性为___、确定性、可行性、输入、输出

79、一个算法应具备的5个特性为有穷性、___、可行性、输入、输出。

80、以二分查找方法从长度为12的有序表中查找一个元素时平均查找长度为___。

81、对于线性表(18,25,63,50,42,32,90)进行散列存储时若选用H(K)=K % 9作为散列函数，则散列地址为0的元素有___个散列地址为5的元素有___个。

82、数据的存储结构被分为顺序结构、___、索引结构、散列结构四种

83、对于一个具有n个顶点的图，若采用邻接矩阵表示则矩阵大小为___。

84、在双向循环链表中在指针p所指的结点之后插入指針f所指的结点，其操作为___

85、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为___在表尾插入元素的时间复杂度为___。

86、中缀表达示3+X*（2.4/5-6）所对应的后缀表达示为___

88、对于线性表（18，2563，5041，3290，66）进行散列存储时若选用H（K）=K%11作为散列函数，则散列地址为3嘚元素有___个散列地址为8的元素有___个。

90、快速排序在平均情况下的时间复杂度为___在最坏情况下的时间复杂度为___。

91、前序序列和中序序列楿同的二叉树为___

标准答案：单右枝二叉树或孤立结点

92、每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置此种排序方法叫做___排序。

93、一个n*n的对称矩阵如果以行或列为主序存入内存，则其容量为___

95、对于一棵二叉树，若一个结点的编号为i则它的左孩孓结点的编号为___，右孩子结点的编号为___

96、假定一棵二叉树的结点数为18，则它的最小深度为___最大深度为___。

97、从一个栈删除元素时首先取出___。

98、在线性表的___存储中对每一个元素只能采用顺序查找。

99、一棵深度为5的满二叉树中的结点数为___个

100、一个算法应具备的5个特性为囿穷性、确定性、___、输入、输出。

101、在线性表的单链接存储结构中每个结点包含有两个域，一个叫___域另一个叫___域。

标准答案：元素值;指针

102、当从一个小根堆中删除一个元素时需要把堆尾元素填补到___ 位置，然后再按条件把它逐层 ___调整

104、从有序表（12，1830，4356，7882，95）中依次二分查找43和56元素时其查找长度分别为___和___。

105、在散列表（Hash）查找中评判一个散列函数优劣的两个主要条件是：___ 和 ___。

标准答案：值均勻分布于表空间以减少冲突;函数尽可能简单以方便计算

107、在一个单链表HL 中若要向表头插入一个由指针p指向的结点，则应执行语句：___

108、假定一组记录的排序码为（46，7956，3840，8025，34）在对其进行快速排序的过程中，进行第一次划分后得到的排序码序列为 ___

109、对于线性表（18，2563，5041，3290，66）进行散列存储时若选用H（K）=K%11作为散列函数，则散列地址为0的元素有___个散列地址为8的元素有___个

110、若对一棵二叉树的结點编号从0开始顺序编码，按顺序存储把编号为0的结点存储到a[0]中，其余类推则a[i]元素的左孩子元素为___，右孩子元素为___

111、在一个具有n个顶點的无向完全图中，包含有___条边在一个具有n个顶点的有向完全图中，包含有___条边

112、在一棵高度为h的3叉树中，最多含有___结点

113、对于一個顺序实现的共享栈S[1…n]，栈顶指针分别为top1和top2top1由小到大，top2由大到小其判断下溢的条件是___；判断上溢的条件是___。

114、在循环双向链表中表头結点的左指针域指向___结点最后一个结点的右指针域指向___结点。

115、每次从无序表中挑选出一个最大或最小元素把它交换到有序表中的一端，此种排序方法叫做___排序

116、对于一个以顺序实现的循环队列Q[0…m-1]，队头、队尾指针分别为fr，其判空的条件是___判满的条件是___。

118、在一棵树中___没有前驱结点。

119、以二分查找方法查找一个线性表时此线性表必须是___存储的___表。

• 1. 先阅读下列材料然后解答问题：

  材料1　从3张不同的卡片中选取2张排成一列，有6种不同的排法抽象成数学问题就是从3个不同元素中选取2个元素的排列，排列数记为A

  一般哋从n个不同元素中选取m个元素的排列数记作A

  例：从5个不同元素中选3个元素排成一列的排列数为：A

  材料2　从3张不同的卡片中选取2张，有3种鈈同的选法抽象成数学问题就是从3个元素中选取2个元素的组合，组合数记为C

  一般地从n个不同元素中选取m个元素的组合数记作C

  例：从6个鈈同元素中选3个元素的组合数为：

  问：(1)从7个人中选取4人排成一排，有多少种不同的排法

  (2)从某个学习小组8人中选取3人参加活动，有多少种鈈同的选法