一、 单项选择题（本大题共20小题，每小题1分，共20分）请将正确选项前的字母填在题后的括号内。
1. 在顺序存储的线性表(a1,a2,...,an)中,删除任意一个结点时所需移动结点的平均次数为（）。
A、nB、n/2C、(n-1)/2 D、(n+1)/2
2.下列算法suanfa2的时间复杂度为____。
int suanfa2(int n)
{ int t=1；
while(t<=n)
t=t*2；
return t；
}
A.O(log2n) B.O(n)C.O(n)D.O(2)
3.____又称为FIFO表。
A.队列B.栈 C.散列表D.哈希表
4.若6行8列的数组以列序为主序顺序存储,基地址为1000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是____。
A.1086 B.1068C.1032 D.答案A,B,C都不对
5.广义表(a,((b,( )),c),(d,(e)))的深度是____。
A.2 B.3 C.4 D.5
6. 若待排序列已基本有序，要使它们完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是（）。
A、归并排序 B、快速排序
C、直接选择排序D、直接插入排序
7.与中缀表达式a+b*c-d等价的前缀表达式是____。
A.+a-*bcdB.*+-abcd
C.-+a*bcdD.abcd+*-
8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次与表中元素____进行比较,。
A.65,15,37B.68,30,37
C.65,15,30D.65,15,30,37
9.对长度为10的表作选择(简单选择)排序,共需比较____次关键字。
A.45B.55C.90 D.110
10.对n个元素的表作快速排序,在最坏情况下,算法的时间复杂度为____。
A.O(log2 n)B.O(nlog2 n)C.O(n)D.O(2)
11.一组记录的关键字经一趟二路归并排序后得到含有5个长度为2的有序表如下：[25，48]，
[16，35]，[79，82]，[23，40]，[36，72]，在此基础上按二路归并排序方法再对该序列进行一趟归并后的结果为（）。
A、16，25，35，48，79，82，23，36，40，72
B、16，25，35，48，23，40，79，82，36，72
C、16，25，48，35，79，82，23，36，40，72
D、16，25，35，48，79，23，36，40，72，82 2n 2n
12.将线性表的数据元素以____结构存放, 查找一个数据元素所需的时间不依赖于表的长度。
A.循环双链表 B单链表 C.哈希(Hash)表 C.一维数组
13.设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有____。
A.a.b,c,d B.a,d,b,c C.b,a,d,c D.c,d,a,b
14. ___ 又是一棵满二叉树。
A.深度为5有31个结点的二叉树
B.有15个结点的完全二叉树
C.哈夫曼(Huffman)树
D.二叉排序树
15.查找哈希(Hash)表,解决冲突的的方法有__B__。
A.除留余数法 B.线性探测再散列法
C.直接地址法 D.链地址法
16.算法指的是（ c ）
A．计算机程序 B．解决问题的计算方法
C．解决问题的有限运算序列 D．排序算法
17.由__D__组成的集合是一个数据对象。
A.不同类型的数据项B.不同类型的数据元素
C.相同类型的数据项D.相同类型的数据元素
18、在一个单链表HL中，若要向q所指结点之后插入一个由指针p指向的结点，则执行 （D）
A、HL=p;p->next=HL B、p->next=HL;HL=p
C、P->next=q->next;q->next=p D、p->next=q->next;q=p>next
19、由权值分别为3，8，10，2，6的叶子结点生成一棵哈夫曼树，该树中双分支结点数为
A、2 B、3 C、4D、5
20．设sub(s,i,j)的功能是返回串s从第i个字符开始长度为j的子串，scopy(s,t)的功能是复制串t到s，若字符串s=`SCIENCESTUDY’，则调用scopy(p,sub(s,1,7))后得到 ( A )
A、p=`SCIENCE’
C、s=`SCIENCE’
A B、p=`STUDY’ D、s=`STUDY 17.下图是一个AOV网，（B）是它的拓扑序列。
C.ADBCE D.CADBE
A.可读性B.正确性 C.时间复杂度 D.并行性 18.对一个算法的评价，不包括如下（D ）方面的内容。
19.递归算法必须使用（A）。
A.线性表B.图 C.栈D.队列 A
20.当稀疏矩阵采用十字链表的链式存储时，它的包括元素的行号、列号、元素本身的信息和（D）的指针域。
A.指向同一行中下一个有效节点的指针
B.指向同一列中下一个有效节点的指针
C.分别指向所在行和列的的下一个有效节点的指针
D.指向头节点的指针
二、填空题（本大题共10小题，每小题2分，共12分）不写解答过程，将正确的答案写在每小题的空格内。
1. 在串S=“structure”中，以t为首字符的子串有
2.
。
3. .第i趟在n-i+l (i=1，2，?，n-l)个记录中选取键值最小的记录作为有序序列的第i个记
录。这样的排序方法称为 选择排序 。
4. 对某非空二叉树进行前序、中序遍历时，所得的结果完全相同（即结点序列一致），则
这棵二叉树必定是 完全二叉树
5. 一个数据结构在计算机中的表示(映象)称为 数据的物理结构
6. .线性表中 __元素的个数 称为表的长度。
7. 从二叉排序树种查找一个元素的时间复杂度是O（log2N）_。
8. 如果一个数据结构的元素个数为n，n>=0，则该数据结构不可能是_空表____。
9. 一个二叉树可以还原为一棵树的条件是该二叉树__中序上将左右子树分开。
10. 有一个5维矩阵的元素k，则k最多有_____24______个后继。
1. 当线性表经常需要查找表中的数据时，应该采用__顺序_________存储结构。
2. 一个栈的输入顺序为123，则栈的可能输出序列有
_____321_________________。
3. 队列的插入是在____队尾部__，在__队头__删除，因此队列又称为_先进后出____。
4. 一棵二叉树有30个节点，其中叶节点有10个，则度为2的节点有_____9______个，度为1的节点有_____6______个。
5. 一棵二叉树有n个节点，则有_____ｎ＋1______指针域被浪费了，所以我们通常用这些没有使用的指针域指向该节点的前驱或者后继，称之为____线索二叉_______树。
6. 如果串采用动态的顺序存储，我们称为___堆存储________。 在循环队列中，为了正确判定队满和队空，常常留一个空间不存储数据，则队满的条件是____（Q.rear+1）%MAXQSIZE=Q.front
_______，队空的条件是___Q.front=Q.rear________。
7. 在线性表的散列存储中，处理冲突的常用方法有_____线性探测再散列、二次探测再散列______和___________两种。
8. 有一个8阶上三角矩阵（行列序号从0开始编号），采用行优先顺序存储为一个顺序表，如果第一个元素的起始地址为L(0)，每个元素需要4个字节，则任意数组元素a[i,j]的存储开始地址是___________。
11. 对某非空二叉树进行前序、中序遍历时，所得的结果完全相同（即结点序列一致），则这棵二叉树必定是____完全二叉树________
12. 一个数据结构在计算机中的表示(映象)称为 ____数据的物理结构____________。 队列是一种先进先出的数据结构，具有出队和入队两种基本操作，如果采用顺序存储，循环队列的出队操作是__p->front= (p->front+1) % MAXLEN
13. _______（队头：front，队列的最大元素个数为m）。
14. 和队列相反，栈是一种具有___先进后出________特点的数据结构。
15. 已知单链表每个节点的结构为：struct node{int data;node *next;}，想在p节点后插入e元素的操作为：
struct node q;
q=(struct node *)malloc(sizeof(struct node));
q->data=e;
q->next=___q->data________;
p->next=____q->next_______;
16. 堆存储是指_____动态分配的空间都在堆上
_______________________________________。 17. 广义表的表头可以是广义表或者独立元素，表尾则一定是 第一个元素去掉剩余的部分____。
18. 排序是指 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。
抽象数据类型定义包括三部分：数据对象、数据关系和基本操作
19. 字符串是指_由数字、字母、下划线组成的一串字符，模式匹配是指________数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串_________________________。
1. 广义表A=((a)，((),()))的表尾是__(a)，((),())___，深度是_3__
____________。
2. 有一个顺序表，数据元素的定义为：
struct data{
char name[10];
int num;
}data;
如果第一个元素的起始地址为L(0)，每个元素需要____________个字节的存储空间，则任意第i个元素的存储首地址是___________。
3. 数据的物理存储结构主要包括顺序和_链式存储__两种情况。
4. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较____7____次就可以断定数据元素X是否在查找表中。 已知P节点是某双向量表的中间节点，在P节点后插入S节点的语句序列是：______________ s->next=p->next;
p->next=s;
5. _________________
三、判断下列叙述是否正确(本大题共5小题，每小题1分，共5分)
1．字符串的长度是指串中不同字符的个数。对
2．存在这样的二叉树，对它采用任何次序遍历结果都相同。对
3．在堆排序中，一个堆的堆根元素一定是一个最小数或最大数 对
4．完全二叉树中，若某个结点没有左孩子，则该结点一定是叶子结点。对
5．线性表的逻辑顺序与存储顺序总是一致的。错
四、试画出下列存储结构图(每小题5分,共15分)
1.数组A[1..2,0..2] 的以列序为主序的顺序存储结构。
2.依次将元素 A,C,D,B 插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈。
3.二叉树的顺序存储结构
:
1.广义表L=（a,b,(c)）的链式存储。
3、如下稀疏矩阵的三元组存储结构。
1.画出数组A[0..2,0..2]的以列序为主序的顺序存储结构图，起始地址为loc，每个元素占有4个字节。
2.依次将元素 A,C,D,B 插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈，指明栈顶和栈底。
4.已知图G中的边为<a,b>,<a,f>,<c,d>,<e,a>,<b,c>，画出该图
五、解答题 (每小题6分,共24分)
1. 设电文中出现字字母A、B、C、D、E、F、G、H每个字母在电文中出现的次数分别是5，25，4，7，9，12，30，8，请画出哈夫曼树，求A,B,C,D的哈夫曼编码及哈夫曼树的WPL。
2.试按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。
(1)试画出插入完成之后的二叉排序树；
(2)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL。
3.1
(3)对该树进行中序遍历,试写出中序遍历序列。
中：5,6,8,9,10,12,15,19,20,25
3.试将森林 F={ T1,T2,T3,T4 }转换为一棵二叉树。
T1T2 T3 T4
4.已知一棵二叉树的前序遍历序列和中序遍历序列分别是：
I,A,B,E,F,G,C,H,D 和 A,E,F,B,I,G,H,C,D
试画出该二叉树。
1. 设电文中出现字字母A、B、C、D、E、F、G、H每个字母在电文中出现的次数分别是5，25，4，7，9，12，30，8，请画出哈夫曼树，求A,B,C,D的哈夫曼编码及哈夫曼树的WPL。
2.试按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。
(1)试画出插入完成之后的二叉排序树；
(2)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL。
(3)对该树进行中序遍历,试写出中序遍历序列。
4.已知一个网的邻接矩阵，画出它的关键路径。aij=0表示节点i到节点j没有有向边aij=k，表示<i,j>的权为k。
3.比较顺序存储、链式存储和哈希存储等几种存储模式
六、阅读题（本大题共3小题，每小题5分，共15分）
1．该算法是用折半查找法在一有序数组中查找key。若找到，返回其下标值，否则返回-1。将算法填充完整。
int BinSearch(DataType list[],int low,int high,DataType key)
{
int mid;
DataType midvalue;
while(low<=high)
{
mid=(low+high)/2;
midvalue=list[mid];
if (key=midvalue) return mid;
else if(key<midvalue)
high=__mid___
else
low=____mid____
}
return –1;
}
2．阅读下面的算法
void mynote(LinkList &L)
{//L是不带头结点的单链表的头指针
if(L&&L->next)
{
q=L；L=L－>next；p=L；
while(p－>next)
p=p－>next；
p－>next=q；q－>next=NULL；
}
}
设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性表。 a2,....,an,a1
3．已知二叉树的存储结构为二叉链表，阅读下面算法。
typedef struct node {
DateType data；
Struct node * next；
}ListNode；
typedef ListNode * LinkList ；
LinkList Leafhead=NULL；
void Inorder (BinTree T)
{
LinkList s；
If(T){
Inorder(T－>lchild)；
If ((!T－>lchild)&&(!T－>rchild)){
s=(ListNode*)malloc(sizeof(ListNode))；
s－>data=T－>data；
s－>next=Leafhead；
Leafhead=s；
}
Inorder(T－>rchild)；
}
}
对于如下所示的二叉树
画出执行上述算法后所建立的结构；
七、算法设计题（选一题，本题共9分）
1.设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上,试将新元素e插入表中第i-1个和第i个元素之间,写出算法。
#include <stdio.h>
int insert(int arr[], int index, int maxlen, int value){
int start_index = index-1;
for (int i = maxlen; i>=start_index; i--) {
arr[i+1] = arr[i];
}
arr[start_index] = value;
return 1;
}
void printarr (int arr[]) {
for (int i = 0; i < 7; i++) {
printf("%d", arr[i]);
}
printf("\n");
}
int main(){
int st[1000] = {1,2,3,4,5,6};
printarr(st);
int maxlen = 6;
insert(st, 3, maxlen, 7);
printarr(st);
return 1;
}
2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出首结点和尾结点的值(data值)；否则输出:”Empty list！”。
1.设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上,试将新元素e插入表中第i-1个和第i个元素之间,写出算法，n<maxen。
2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出首结点和尾结点的值(data值)；否则输出:”Empty list！”。
1.设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上(n<maxlen),试将新元素e插入表中第i-1个和第i个元素之间,写出算法。
2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出首结点和尾结点的值(data值)；否则输出:”Empty list！”。
1.设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上,试将新元素e
插入表中第i-1个和第i个元素之间,写出算法，n<maxen。
2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出首结点和尾结
点的值(data值)；否则输出:”Empty list！”。
1.设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上(n<maxlen),试将新元素e插入表中第i-1个和第i个元素之间,写出算法。
2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出首结点和尾结点的值(data值)；否则输出:”Empty list！”。
www.99jianzhu.com/包含内容：建筑图纸、PDF/word/ppt 流程，表格，案例，最新,免费下载,施工方案、工程书籍、建筑论文、合同表格、标准规范、CAD图纸等内容。