当前位置:首页 >> 学科竞赛 >> 数据结构期末试题及答案 2

数据结构期末试题及答案 2


D
一、单项选择题 1、在以下的叙述中,正确的是( B )。

A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出 2、判定一个循环队列qu(最多元素为m0)为空的条件是( A. qu->front==qu->rear B. qu->f

ront!=qu->rear C. qu->front=(qu->rear+1)%m0 D. qu->front!=(qu->rear+1)%m0 3、 向一个栈顶指针为hs的链栈中插入一个s所指结点时, 则执行( A. hs->next=s; B. s->next=hs->next;hs->next=s; C. s->next=hs;hs=s; D. s->next=hs;hs=sh->next 4、串是一种特殊的线性表,其特殊性体现在( B A. 可以顺序存储 C. 可以链接存储 )。 C )。 A )。

B. 数据元素是一个字符 D. 数据元素可以是多个字符

5、设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存 放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i≥j),在 一维数组B的下标位置k的值是( B )。 A. i(i-1)/2+j-1 B. i(i-1)/2+j

第 1 页 (共 1 页)

C. i(i+1)/2+j-1

D. i(i+1)/2+j A )。

6、将递归算法转换成对应的非递归算法时,通常需要使用( A. 栈 B. 队列 C. 链表 D. 树

7、 树的基本遍历策略可分为先根遍历和后根遍历叉树的基本遍历策略可 分为先序遍历、中序遍历和后序遍历。这里,我们把由树转化得到的二 叉树叫做这棵树对应的二叉树。结论_A___是正确的。 A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D. 以下都不对 8、对一个满二叉树,m个树叶,n个结点,深度为h,则( D A. n=h+m B. h+m=2n C. m=h-1 D. )。

n=2h-1

9、具有7个顶点的无向图至少应有( A A. 5 B. 6 C. 7

)条边才能确保是一个连通图。 D. 8

10、判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可 以利用( D )。 B. D. 求最短路径的Dijkstra方法 深度优先遍历算法

A. 求关键路径的方法 C. 宽度优先遍历算法

11、 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分 查找值为82的结点时,( C A. 1 B. 2 )次比较后查找成功。 C. 4 D. 8

12、如果要求一个线性表既能较快地查找,又能适应动态变化的要求, 可以采用__A___查找方法。 A. 分块 B. 顺序 C. 二分 D. 散列

13、在所有排序方法中,关键字比较的次数与记录的初始排列次序无关

第 2 页 (共 2 页)

的是____D_____。 A. 希尔排序 B. C 起泡排序 C. 插入排序 D. 选择排序

14、快速排序方法在(

)情况下最不利于发挥其长处。

A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 15、索引无序文件是指( A )。

A. 主文件无序,索引表有序 B. 主文件有序,索引表无序 C. 主文件有序,索引表有序 D. 主文件无序,索引表无序 二、填空题(每空 2 分,共 30 分) 16、下面程序段的时间复杂度是__O(m*n)_____。 for ( i=0;i<n;i++) for (j=0; j<m; j++) a[i][j]=0; 17、向栈中压入元素的操作是___先移动栈顶指针,后存入元素 。 18、 在hq的链队中, 判定只有一个结点的条件是_hq->front==hq->rear 。 19、已知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储 单元,并且第一个元素的存储地址是LOC(A[0][0]),A[i][j]的地址是 _LOC(A[0][0])+(n*i+j)*k_____。 20、有如下递归方程: void print(int w) { int i;

第 3 页 (共 3 页)

if {

(w!=0)

print(w-1); for (i=1;i<=w;i++) print(“%3d”,w); rpintf(“/n”);

} } 调用语句print(4)结果是__答 1 2 2 3 3 3 4 4 4 4 ______ 21、 广义表(a,(a,b),d,e,((i,j),k)) 的长度是________, 深度是_____。 22 、 以 数 据 集 {4,5,6,7,10,12,18} 为 结 点 权 值 所 构 造 的 哈 夫 曼 树为 _____,其带权路径长度为________。 23、已知图G的邻接表如下图所示,其从顶点v1出发的深度优先搜索序列 为_v1,v2,v3,v6,v5,v4 , 其 从 顶 点 v1 出 发 的 宽 度 优 先 搜 索 序 列 为 _ v1,v2,v5,v4,v3,v6 。

24、在各种查找中,平均查找长度与结点个数n无关的查法方法是_哈希 表查找法 。 25、 在对一组记录{54,38,96,23,15,72,60,45,83}进行直接插入排序时,

第 4 页 (共 4 页)

当把第 7 个记录 60 插入到有序表时,为寻找插入位置需比较__3 _次。 26、顺序查找法的平均查找长度为_(n+1)/2__;二分查找法的平均查找 长度为___((n+1)*log2(n+1))/n-1 。 三、解答操作题(每小题 5 分,共 20 分) 27、已知序列{503,87,512,61,908,170,897,275,653,462},采用基数排 序法对该序列作升序排序时的每趟的结果。 答:初始:503,87,512,61,908,170,897,275,653,462 第1趟(按个位排序)170,61,462,512,503,653,475,87,897,908 第2趟(按十位排序)503,908,512,653,61,462,170,175,87,897 第3趟(按百位排序)61,87,170,275,462,503,512,653,897,908

28、设给定权集w={2,3,4,7,8,9},度构造关于w的一棵哈夫曼树, 并求其 加权路径长度wpl。 答:加权路径长度wpl=7×2+8×2+4×3+2×4+3×4+9×2=80 29、对下图所示的树: (1)转换成对应的二叉树形式,并且说明转换规则; (2)写出前序、中序、后序遍历的结果;

答:(2) 前序:abcejfdghki

中序:jefcgkhidba 后序:jfekihgdcba

第 5 页 (共 5 页)

30.现有稀疏矩阵 A 如下图所示,要求画出以下几种表示法。 (1)三元组表示法 (2)带行指针向量的单链表表示法 (3)十字链表示法。 四、算法阅读题(每小题6分,共12 分) 31、下列算法的功能是实S串的逆序 (串均采用顺序存储方式),请在空白处填入适当的内容。 SeqString *invert (SegString *s) { int i; char temp for (i=0; i<s->length/2; i++) { temp=s->ch[i]; s->ch[i]=s->ch[ s-length-i+1 Temp; ];

s->ch[s->length-i+1]= } Return(s) ;}

32.下列算法的功能是实现链栈的进栈运算,请在空白处填入适当的内 容。 链栈的类型定义如下: Typedef struct stacknode { DataType data; Struct stacknode *next; } StackNode; Typedef struct {

第 6 页 (共 6 页)

StackNode *top; }LinkStack; Void Push(LinkStack *s,DataType x) { StackNode p; *p=(StackNode *)malloc(sizeof(StackNode)); p->data= p->data=x; ; p->next= p->next=s->top; ; s->top= s->top=p;; } 五、算法设计题 33、假设二叉树采用链接方法存储,编写一个函数复制一棵给定的二叉 树。结点结构为: 答: Btree *copy(btree *b) { Btree *p; If (b!=NULL) { P=(btree *)malloc(sizeof(btree)) p->data=b->data; p->left=copy(b->left); p->right=copy(b->right); return(p); } Else return(NULL); }

第 7 页 (共 7 页)


更多相关文档:

《数据结构》期末考试试题及答案

数据结构期末考试试题及答案 (2003-2004 学年第 2 学期) 贵州大学理学院数学系信息与计算科学专业 一、 单项选择题 1.对于一个算法,当输入非法数据时,也...

数据结构期末试题及答案

数据结构期末试题及答案_其它考试_资格考试/认证_教育专区。E 卷一、单项选择题...18、 评价一个数据结构, 基本来说有两条, 一条是___, 是___。 19、栈...

2015年数据结构期末考试题及答案

2012 年数据结构期末考试题及答案 一、选择题 1.在数据结构中,从逻辑上可以把...D.数据 2.数据结构在计算机内存中的表示是指 A.数据的存储结构 元素之间的...

2套通用期末数据结构试题及答案

2套通用期末数据结构试题及答案_其它课程_高中教育_教育专区。数据结构试卷(一) 一、单选题(每题 2 分,共 20 分) 1. 栈和队列的共同特点是( )。 A.只允...

数据结构期末考试试题及答案

数据结构期末考试试题及答案_理学_高等教育_教育专区。数据结构期末考试试题及答案...2.void delete (LinkList &head , ElemType x, ElemType y) { //在头...

《数据结构》期末考试试题及答案

数据结构期末考试试题及答案 (2003-2004 学年第 2 学期) 单项选择题 1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1.对于...

数据结构试卷及参考答案_2

数据结构试卷及参考答案_2_工学_高等教育_教育专区。数据结构试卷()一、选择题(24 分) 1.下面关于线性表的叙述错误的是( )。 (A) 线性表采用顺序存储必须...

数据结构期末考试题

数据结构期末考试题_从业资格考试_资格考试/认证_教育专区。一、 单选题(每题 ...temp=p->data; delete p; return temp; } 参考答案一、 1.B 2.A 、...

《数据结构》期末考试题及答案

数据结构期末考试题及答案_计算机软件及应用_IT/计算机_专业资料。《数据结构...(n2) 2.六个元素按照 6,5,4,3,2,1 的顺序入栈,下列哪一个是合法的出...
更多相关标签:
数据库期末试题及答案 | 数据结构试题及答案 | 数据结构期末考试题 | 数据结构期末考试 | 数据结构期末复习 | 数据结构期末试卷 | 数据结构期末试题 | 数据结构期末考试试卷 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com