加载中…
《数据结构》试题
(2007-06-29 22:03:59)| 分类： 专升本试题 |
一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号
(A,B,C,D)写在下表中,答题写在其它地方无效；每小题1分,共11分)
题号 1 2 3 4 5 6 7 8 9 10 11
答案
1.数据的不可分割的基本单位是____。
A.元素 B.结点 C.数据类型 D.数据项
2.下列算法suanfa2的时间复杂度为____。
int suanfa2(int n)
{ int t=1；
while(t<=n)
t=t*2；
return t；
}
A.O(log2n) B.O(2n) C.O(n2) D.O(n)
3.____又称为FIFO表。
A.队列 B.散列表 C.栈 D.哈希表
4.若6行8列的数组以列序为主序顺序存储,基地址为1000,每个元素占2个
存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是____。
A.1086 B.1032 C.1068 D.答案A,B,C都不对
5.广义表(a,((b,( )),c),(d,(e)))的深度是____。
A.5 B.4 C.3 D.2
6.有n(n>0)个结点的完全二叉树的深度是____。
A.élog2(n)ù B.élog2(n)+1ù
C.ëlog2(n+1)û D.ëlog2(n)+1û
7.与中缀表达式a+b*c-d等价的前缀表达式是____。
A.+a-*bcd B.*+-abcd
C.-+a*bcd D.abcd+*-
8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次 与表中元素____进行比较,。
A.65,15,37 B.68,30,37
C.65,15,30 D.65,15,30,37
9.对长度为10的表作选择(简单选择)排序,共需比较____次关键字。
A.45 B.90 C.55 D.110
10.对n个元素的表作快速排序,在最坏情况下,算法的时间复杂度为____。
A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n )
共5 页第1页
11.对长度为10的表作2_路归并排序,共需移动____次(个)记录。
A.20 B.45 C.40 D.30
二、填空(每空1分,共11分)
1.一个数据结构在计算机中的表示(映象)称为 ________________ 。
2.线性表中 ____________________________ 称为表的长度。
3.栈中元素的进出原则为 _____________________ 。
4.设数组A[1..10,1..8]的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素A[4,5]的存储地址为_____；若以列序为主序顺序存储,则元素A[4,5]的存储地址为______。
5.一棵深度为6的满二叉树有______个非终端结点。
6.若一棵二叉树中有8个度为2的结点,则它有_____个叶子。
7.顺序查找n个元素的顺序表,当使用监视哨时,若查找成功,比较关键字的次数至少为____次, 最多为____次；若查找失败,比较关键字的次数为____次。
8.对长度为400的表采用分块(区)查找,最理想的块长为____。
三、回答下列问题 (每小题5分,共10分)
1.线性表的存储结构,在什么情况下采用顺序结构? 为什么?
2.二叉树有哪几种基本形态? 画图说明之。
四、试画出下列存储结构图(每小题4分,共20分)
1.数组A[1..2,0..2] 的以列序为主序的顺序存储结构。
共5 页第2页
2.依次将元素 A,C,D,B 插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈。
3.二叉树的顺序存储结构:
4.图的邻接矩阵:
5.有向图的逆邻接表:
五、求解下列问题 (每小题6分,共24分)
1.给定30个字符组成的电文:
D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D
试为字符 A、B、C、D、E、F 设计哈夫曼(Huffman)编码。
(1)画出相应的哈夫曼树；
(2)分别列出 A、B、C、D、E、F 的哈夫曼码；
(3)计算该树的带权路径长度WPL。
共5 页第3页
2.试按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。
(1)试画出插入完成之后的二叉排序树；
(2)若查找元素17,它将依次与二叉排序树中哪些元素比较大小?
(3)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL。
(4)对该树进行中序遍历,试写出中序遍历序列。
3.试将森林 F={ T1,T2,T3,T4 }转换为一棵二叉树。
T1 T2 T3 T4
4.找出下面网络的最小生成树。
六、填空题(在算法中有下划线____的位置填空,使之成为完整、正确的算法)
算法说明:已知r[1..n]是n个记录的递增有序表,用折半查找法查找关键字为k的记录,若查找失败,则输出”Failure”,返回零；否则输出”Success”,并返回该记录的序号值。(共8分)
算法(C函数):
共5 页第4页
int bin_search(struct arecord r[],int n,k:keytype)
/* r[1..n]为n个记录的递增有序表,k为关键字 */
{ int low, mid, hig ；
low=1； hig=n ； /* 各变量初始化 */
while( _____ )
{ mid=___________________ ；
if(k<r[mid].key) ____________________ ；
else if(k==r[mid].key)
{ _____________________ ；
_____________________ ；
}
else _____________________ ；
}
__________________ ； __________________ ；
}
七、算法设计(算法中必须有注释,每小题8分,共16分)
1.设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上,试将新元素e插入表中第i-1个和第i个元素之间,写出算法。
2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出首结点和尾结点的值(data值)；否则输出:”Empty list！”。
共5 页第5页
网计(专升本)《数据结构》试题(模B)2004-5-1
一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号
(A,B,C,D)写在下表中,答题写在其它地方无效；每小题1分,共11分)
题号 1 2 3 4 5 6 7 8 9 10 11
答案
1.数据的基本单位是____。
A.结点 B.数据元素 C.数据类型 D.数据项
2.下列算法suanfa1中语句"x=x*2；"的执行次数是____。
void suanfa1(int n)
{ int i,j,x=1；
for(i=1；i<=n；i++)
for(j=i；j<=n；j++)
x=x*2；
printf("%d",x)；
}
A.n(n-1)/2 B.n(n+1)/2 C.n2 D.énlog2nù
3.当需要随机查找线性表的元素时,宜采用____作存储结构。
A.双向链表 B.循环链表 C.顺序表 D.单链表
4.若8行6列的数组以行序为主序顺序存储,基地址为2000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是____。
A.2086 B.2032 C.2068 D.答案A,B,C都不对
5.广义表(a,(b),c,(d,(e)))的表尾是____。
A.(d,(e)) B.(d,(e))）
C.(b),c,(d,(e)) D.((b),c,(d,(e)))
6.____是"Yu**Jia**Shan"的子串。
A.Yu B."jia" C."**Shan" D."YuJiaShan"
7.无向完全图的邻接矩阵是____矩阵。
A.对称 B.上三角 C.下三角 D.稀疏
8.有n(n>0)个结点的完全二叉树的深度是____。
A.élog2(n)+1ù B.élog2(n)-1ù
C.ëlog2(n)-1û D.ëlog2(n)+1û
9.与中缀表达式a-b/c+d等价的前缀表达式是____。
A.-a+/bcd B./-+bcd
C.+-/bcd D.abcd-/+
10.对有3600个记录的索引顺序表(分块表)进行查找,最理想的块长为____。
A.1800 B.60
C.1200 D.élog2 3600ù
共5 页第1页
11.对n个元素的表作堆排序,在最坏情况下,算法的时间复杂度为____。
A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n )
二、填空题(每空1分,共11分)
1.一个算法具有5个特性:__________________、__________________、________________、有零个或多个输入、有一个或多个输出。
2.设长度为n的线性表顺序存贮,若在它的第i-1和第i个元素之间插入一个元素, 共需移动 _________ 个元素(1<i≤n)。
3.一个字符串中 __________________________ 称为该串的子串。
4.树中结点A的 ____________________ 称为结点A的度。
5.一棵深度为4的二叉树最多有 _______ 个结点。
6.具有10个顶点的无向图,边的总数最多为 _____________ 。
7.顺序查找n个元素的顺序表,当不使用监视哨时,若查找成功,比较关键字的次数最多为 ____ 次；若查找失败,比较关键字的次数为 _____ 次。
8.折半查找有序表( 2,4,6,12,20,28,38,50,70,100 ),若查找表中元素12,它依次与表中元素 ___________________ 比较大小。
三、回答下列问题 (每小题5分,共10分)
1.线性表的存储结构,在什么情况下采用链接表(如:单链表)结构?为什么?
2.空格串与空串有区别? 举例说明之。
共5 页第2页
四、试画出下列存储结构图(每小题5分,共20分)
1.试画出下列稀疏矩阵以列序为主序的三元组表。
稀疏矩阵
2.试画出下列二叉树的中序线索二叉树存储结构图。
二叉树
3.试用孩子兄弟(左孩子右兄弟)表示法画出下列树的存储结构图。
树
4.试画出下列有向网的逆邻接表。
有向网
共5 页第3页
五、求解下列问题 (每小题6分,共24分)
1.已知二叉树的前序遍历序列和中序遍历序列分别是：
B,A,C,D,F,E,G和D,C,A,F,G,E,B,
试画出该二叉树。
2.试按表(25,15,19,24,20,5,16,45,40,38)中元素的排列次序,将所有元素插入一棵初始为空的二叉排序树中,使之仍是一棵二叉排序树。(1)试画出插入完成之后的二叉排序树；(2)若查找元素17,它将依次与二叉排序树中哪些元素比较大小?(3)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL；(4)对该树进行中序遍历,试写出中序遍历序列。
3.试用权集合{4,6,5,12,2,1,13},构造赫夫曼(Huffman)树,(1)列出构造过程, (2)分别计算该赫夫曼树的路径长度和带权路径长度。
4.找出下面网络的最小生成树:
共5 页第4页
六、执行下面的C程序,指出输出结果。(8分)
#include<stdio.h>
#include<stdlib.h>
struct node
{ char data；
struct node *next；
}；
void link_list(struct node *p)
{ while(p!=NULL)
{ printf("%c",p->data)； p=p->next；
}
printf("\n")；
}
main( )
{ char ch；
struct node *q,*p,*f,*head=NULL；
for (ch='A'；ch<'F'；ch++)
{ p=(struct node *)malloc(sizeof(struct node))；
p->data=ch； p->next=head； head=p； link_list(p)；
}
p=head； head=NULL；
while(p!=NULL)
{ q=p； p=p->next； q->next=head； head=q； f=head；
while(f->next!=NULL)
{link_list(head)； f=f->next->next；
}
}
}
七、算法设计(算法中必须有注释,每小题8分,共16分)
1.设n个元素的线性表顺序存储在一维数组 st[1..maxlen] 的前n个位置上,试写出算法:删除表中第i(1≤i≤n)个元素。
2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出:最大结点和最小结点的值(data值)；否则,输出:“Empty list”。
共5 页第5页
网计(专升本)《数据结构》试题(模C) 2004-5-1
一、选择题(从下列各题的4个备选答案中选出1至2个正确答案,将其代号(A,B,C,D)写在下表中,答题写在其它地方无效；每小题1分,共15分)
题号 1 2 3 4 5 6 7 8 9 10 11 12 12 14 15
答案
1.由____组成的集合是一个数据对象。
A.不同类型的数据项 B.不同类型的数据元素
C.相同类型的数据项 D.相同类型的数据元素
2.____是线性表。
A.(孔子,诸葛亮,曹雪芹) B.{A,B,C,D}
C.{10,11,12,13,14} D.(1,2,3,...)
3.____ 是表示线性数据结构的。
A.循环链表 B.邻接多重表 C.孩子链表 D.单链表
4.将线性表的数据元素以____结构存放, 查找一个数据元素所需
的时间不依赖于表的长度。
A.循环双链表 B.哈希(Hash)表 C.一维数组 D.单链表
5.设数组A[1..8,1..10]的基地址为4000, 每个元素占2个存储单元,若以列序为主序顺序存储,则元素A[4,7]的存储地址是____。(假定无第0行第0列元素)
A.4072 B.4104 C.4102 D.4074
6.设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有_____。
A.a.b,c,d B.a,d,c,b C.b,a,d,c D.c,d,a,b
7.___ 又是一棵满二叉树。
A.二叉排序树 B.深度为5有31个结点的二叉树
C.有15个结点的完全二叉树 D.哈夫曼(Huffman)树
8.深度为k的满二叉树有____个分枝结点。
A.2k-1 B.2k-1-1 C.2k+1 D.2k-1+1
9.具有n(n>0)个结点的完全二叉树的深度为_____。
A.élog2(n)ù B.ëlog2(n)û +1
C.élog2(n+1)ù D.ëlog2(n+1)û
10.折半查找20个记录的有序表,若查找失败,比较关键字的次数____。
A.最多为6 B.最多为5 C.最少为3 D.最少为4
11.折半查找有序表(2,5,8,20,25,36,40,60),若查找元素60,需依次与
表中元素____进行比较。
A.25,40,60 B.25,40 C.20,36,40,60 D.20,36,40
12.查找哈希(Hash)表,解决冲突的的方法有____。
A.除留余数法 B.线性探测再散列法 C.直接地址法 D.链地址法
共5页第1页
13.对有10个记录的表作简单选择排序,需要比较___次关键字。
A.100 B.45 C.50 D.90
14.对有n个记录的表作快速排序,在最坏情况下,算法的时间复杂度是____。
A.O(n) B.O(n2) C.O(nlog2n) D.O(n3)
15.一个排序算法时间复杂度的大小____有关。
A.与所需比较关键字的次数 B.与该算法的稳定性
C.不与所需移动记录的数目 D.与所需辅助存储空间的大小
二、画图题(每小题4分,共20分)
1.依次输入元素X,Y,Z, 插入到一个初始状态为空的链式栈中,试画出空的链式栈和每插入一个元素之后的链式栈示意图。
2.试用双亲表示法画出下列树T的存储结构图。
3.试画出有3行4列元素的二维数组B的以列序为主序的顺序存储结构图。
4.试画出下列图的邻接表。
图
共5页第2页
5.已知一棵二叉树的前序遍历序列和中序遍历序列分别是：
I,A,B,E,F,G,C,H,D 和 A,E,F,B,I,G,H,C,D
试画出该二叉树。
三、求解问题(每小题7分,共28分)
1.用算符优先法求下列算术表达式的值,试简要说明求值过程,画出*作数栈 和运算符栈的主要变化过程。
12+20/(10-2*3)
2.给定电文(文本):
F F A A A B B B A A A B B C C C D E G G G
试为字符 A、B、C、D、E、F、G设计哈夫曼(Huffman)编码:(1)画出相应的哈夫曼树,列出各字符的哈夫曼码；(2)计算该哈夫曼树的带权路径长度。
共5页第3页
3.假定后序遍历二叉树的结果是A,C,B,(1)试画出所有可得到这一结果的不同形态的二叉树；(2)分别写出这些二叉树的中序遍历序列。
4.假定对20个记录的表作折半查找,(1)试画出描述折半查找过程的判定树；(2)若每个记录的查找概率相等,试计算查找成功时的平均查找长度。
四、分析算法回答问题(每小题10,共20分)
1.算法(C函数)
int suanfan(int n)
{ int i,j,sum=0；
for (i=0；i<=n；i++)
{ for (j=i；j<n；j++) sum++；
printf("i=%d,j=%d,sum=%d\n",i,j,sum)；
}
return sum；
}
试回答问题:
(1)"j<n"共执行多少次？
(2)"sum++；"共执行多少次？
(3)算法的时间复杂度是多少？
(4)假定n=4,算法的输出结果是什么？(5)假定n=4,算法的返回值是多少？
共5页第4页
2.设二叉树T的存储结构为二叉链表,结点结构定义如下：
struct node
{ char data； //data为字符型
struct node *lchild,*rchild； //指向左右孩子的指针
}；
设root为二叉树T的根指针,(1)对二叉树T执行算法traversal(root),试指出其输出结果；(2)假定二叉树T共有n个结点,试分析算法traversal(root)的时间复杂度。
算法(C函数)如下：
void traversal(struct node *root)
{ if(root)
{ printf("%c",root->data)；
traversal(root->lchild)；
printf("%c",root->data)；
traversal(root->rchild)；
}
}
五、设计算法:输入一个m*n的整数矩阵,如果各个元素互不相同,则输出信息"没有重码!"；否则输出信息"有重码:"和重码值(相同的元素)。
1.用C语言写出所用数据结构的类型定义和算法；
2.分析算法的时间复杂度。
(共17分
喜欢
0
赠金笔
前一篇：专升本考试万能作文模板
后一篇：英语写作