08_09(2)数据结构试卷A
- 格式：doc
- 大小：60.50 KB
- 文档页数：6
一、填空题（每空1分，共18分）
1、算法的5个重要特性是__________、___________、________、输入和输出。
2、单链表中，除首元素结点外，其它任一元素结点的存储位置由___________指示。
3、在双向链表中，欲在p 所指结点之前插入一个由s 指向的结点，请完成有关操作。
s->prior=p->prior; p->prior=s;
____________________； s->next=p;
4、对于栈只能在________插入和删除元素；对于队列只能在_________插入元素和_______删除元素。
5、在模式匹配的KMP 算法中用到了一个next 函数，若next[j]=k ，则说明在模式串T 中存在一个与“T 1T 2...T k-1”相等的子串“_________________”。
6、在对N 个元素进行冒泡排序时，最少的比较次数是_________。
7、假设有二维数组A 6 8，每个元素用相邻的6个字节存储，存储器按字节编址。
已知A 的起始存储位置（基地址）为1000，则数组A 共占用____________个字节的存储单元，按行存储时，元素A 25的第一个字节的地址为_____________。
8、若以{4，5，6，7，8 }作为叶子结点的权值构造哈夫曼树，则其带权路径长度为______。
9、采用分块查找时，若表中共有256个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分_____个结点为最佳。
10、广义表g=( ())的表头是__________，表尾是__________。
11、假定对长度为300 的有序表进行折半查找，则对应的判定树的高度为_______，最后一层的结点数为______。
二、单项选择题（每空1分，共10分）
1、线性结构的顺序存储结构是一种 ______的存储结构，线性结构的链式存储是一种 ______的存储结构。
A. 随机存取
B. 顺序存取
C. 索引存取
D. 散列存取 2、执行下面程序段时，S 语句的执行次数为_________。
for (int i=1;i<=n-1;i++)
for (int j=i+1;j<=n;j++) S;
A. (1)/2n n -
B. 2
/2n C. (1)/2n n + D. n
3、将两个各有N 个元素的有序表归并为一个有序表，其最少的比较次数是________。
A. N; B. 2N-1; C. 2N; D. N-1
4、已知4个元素进栈的顺序依次为A,B,C,D ，则下面哪一个出栈序列是不可能得到的_____。
A. ABCD; B. CBAD; C. CADB; D. BCAD
5。
图1
A. V 1 , V 4 , V 6 , V 2 , V 5 , V 3
B. V 1 , V 2 , V 3 , V 4 , V 5 , V 6
C. V 1 , V 4 , V 2 , V 3 , V 6 , V 5
D. V 1 , V 2 , V 4 , V 6 , V 3 , V 5
6、G 是一个非连通无向图，共有28条边，则该图至少有_______个顶点。
A. 8
B. 9
C. 10
D. 12
7、在下面算法中，________算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。
A. 堆排序
B. 冒泡排序
C. 插入排序
D. 快速排序 8、与其它查找方法相比，散列查找法的特点是_______。
A. 通过关键字的比较进行查找
B. 通过关键字计算元素的存储地址进行查找
C. 通过关键字计算元素的存储地址并进行一定的比较进行查找
D. 以上都不是
9、某二叉树的层序序列是abcdefgh ，中序序列是dbgehacf ，则该树的后序序列是________________。
A . fahgbec B. eagbfdc C. dghebfca D. acdbfge
三、应用题（每小题9分，共36分） 1．对图2所示的二叉树，要求
图2
（1）将其转换为树或森林，画出转换后的结果。
（2）给出对该树或森林分别进行先根遍历和后根遍历得到的结点序列。
2．无向图如图3所示，画出从顶点A 出发用普里姆（prim ）算法构造最小生成树的过程，
F H
G E A I
C D B
并给出一个从顶点A出发的深度优先搜索序列。
图3
3．使用哈希函数H(key)=key % 11，把一个整数值转换成哈希表下标，现要把数据1、13、12、34、38、33、27、22插入到哈希表（表1）中。
（1）使用线性探测再散列法构造哈希表，请在表1所示的哈希表中与哈希地址对应的位置上，填写出相应的关键字值和元素插入时的探查次数。
（2）假设查找每个元素的概率相同，求出查找成功时的平均查找长度。
表1
4、试说明快速排序的基本思想，并给出对关键字序列{ 47，33，61，82，72，11，25，57}进行快速排序过程的示意（即画出每一趟排序后的关键字序列）。
四、算法阅读题（每小题8分，共16分）
1、阅读下面算法，按要求作答，其中Push(S, d)表示将数据元素d压入栈S中，Pop(T,d)表示T的栈顶元素出栈并存入d中。
int algo (Stack S , int e)
{
int d; Stack T;
InitStack(T);
while(!StackEmpty(S)) {
Pop(S,d);
if(d!=e) Push(T, d);
} //while
while(!StackEmpty(T)) {
Pop(T, d);
Push(S, d);
}
}
（1）假设栈S中的原始数据从栈底至栈顶依次为：3，5，7，12，5，6，8；e的值为5。
请写出算法执行完后栈S中从栈底至栈顶的数据元素序列。
（2）简述该算法的功能。
2、已知数组a中存放着两组数据元素序列（a0，a1，．．．，a m-1，b0，b1，．．．，b n-1）。
下面算法利用原存储空间将a中的数据元素序列就地互换为（b0，b1，．．．，b n-1，a0，a1，．．．，a m-1），算法思想可以描述为：
（1）把数组a中的数据元素序列（a0，a1，．．．，a m-1，b0，b1，．．．，b n-1）就地逆置为（b n-1，．．．，b1，b0，a m-1，．．．，a1，a0）。
（2）把数组a中的数据元素序列（b n-1，．．．，b1，b0，a m-1，．．．，a1，a0）就地逆置为（b0，b1，．．．，b n-1，a m-1，．．．，a1，a0）。
(3) 把数组a中的数据元素序列（b0，b1，．．．，b n-1，a m-1，．．．，a1，a0）就地逆置为（b0，b1，...，b n-1，a0，a1...，a m-1）。
根据上述算法思想，请在空缺处填上适当的语句，以完善算法功能。
void converse (ElemType a[],int low,int high)
{ //将数组a中自下标low 至high的一段数据元素逆置
int n,i;
ElemType x;
n= (high-low+1)/2; // n 为循环次数
for(i=0;i<n;i++)
{ x=a[low+i];
____________;
____________;
}
}
void exchange (ElemType a[],int m,int n)
{
converse(a,0,m+n-1);//将数组a中的m+n个元素就地逆置
●______________________________;
❍______________________________;
}
五、算法设计（每小题１０分，共２０分）
下面两题的数据类型定义和函数首部均已给出，请按要求完成算法设计。
１．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子结点的个数。
typedef struct Tnode{
TelemType data;//结点数据域
struct Tnode *firstchild *nextsibling;//指向长子和右兄弟的指针
}CSnode,*CStree;
void leafcount(CStree T , int *count)
{ // 统计以孩子—兄弟链表存储表示的树T的叶子结点数目，结果存于count 所指单元，// T为指向根结点的指针
} //leafcout
2、写出二分查找的递归算法。
#define MaxL <表中最多记录数>
typedef struct{
KeyType key; // 主关键字域
OtherType otherinfo; // 其它数据域
}NodeType;
typedef NodeType SeqList[MaxL+1];// 顺序表类型
int binsearch (SeqList R , int low ,int high , KerType key )
{ // 折半查找的递归算法。
R为有序顺序表，low和high 分别为查找区间的下限和上限，// key为待查关键字
} // binsearch。
