说课吧首页 阅览说课吧 → 说课稿 → 高职中职精品课 → 计算机专业> 正文

数据结构期末试卷

Tags： 数据结构
字号：T|T
本站微信

数据结构期末试卷B

一、判断题：（共10分，每题1分）
1、满二叉树也是完全二叉树。（    ）
2、二叉树可以用0≤度≤2的有序树来表示。（   ）
3、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（    ）
4、带权连通图中某一顶点到图中另一顶点的最短路径不一定唯一。（    ）
5、在n个结点的无向图中,若边数少于n-1,则该图必是非连通图。（    ）
6、树的带权路径长度最小的二叉树中必定没有度为1的结点。（    ）
7、哈希表的查找无需进行关键字的比较。（    ）
8、折半查找方法可以用于按值有序的线性链表的查找。（    ）
9、对一个堆按层次遍历，不一定能得到一个有序序列。（    ）
10、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。（    ）
二、填空题：（共20分，每空2分）
1、    度数为0的结点，即没有子树的结点叫作________结点。同一个结点的儿子结点之间互称为________结点。
2、 在具有n个结点的二叉链表中，有_______个空链域。
3、   一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个______________。
4、给定序列{100, 86, 48, 73, 35, 39, 42, 57, 66, 21}, 按堆结构的定义, 则它是一个______堆。
5、在进行直接插入排序时, 其数据比较次数与数据的初始排列________关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__________关。
6、结点关键字转换为该结点存储单元地址的函数H称为_________或叫___________。
7、对n个关键字的序列进行快速排序，平均情况下的空间复杂度为_______。
三、选择题：（共20分，每题2分）
1、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为______。
A.98                 B.99         
C.50                 D.48
2、堆的形状是一棵_______。
A.二叉排序树             B.满二叉树   
C.完全二叉树            D.平衡二叉树
3、对于哈希函数H(key)=key MOD 13，被称为同义词的关键字是_______
A.35和41              B.23和39    
C.15和44              D.25和51
4、指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找12，需做多少次比较。 ______
A、2                  B、3         
C、4                  D、5
5、假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的边时间复杂度是：________
A.O（n）            B.O（e）   
C.O（n+e）          D.O（n*e）
6、从二叉排序树中查找一个元素时，其时间复杂度大致为________。
A、 O(n)                        B、 O(1)     
C、 O(log2n)                    D、 O(n2)
7、由权值分别为3,8,6,2,5的叶子结点生成一棵赫夫曼树，它的带权路径长度为________。
A、 24                             B、 48     
C、 72                             D、 53
8、设有字符序列{Q、H、C、Y、P、A、M、S、R、D、F、X}，一趟排序的结果为{F、H、C、D、P、A、M、Q、R、S、Y、X}，则是下列哪个排序算法。_____
A、起泡排序                  B、初始步长为4的shell的排序
C、二路归并排序              D、以第一个元素为分界元素的快速排序
9、一个无向连通图的生成树是含有该连通图的全部顶点的_______。
A.极小连通子图            B.极小子图   
C.极大连通子图          D.极大子图
10、图的广度优先遍历类似于二叉树的_______。
A.先序遍历              B.中序遍历     
C.后序遍历              D.层次遍历
 
 
 
 
 
 
 
 
 
 
四、应用题：（共28分，每题4分）
1、如图所示的二叉树完成中序遍历、后序遍历、先序遍历，并画出中序线索化的二叉树。

A

 
C
B
D
E
F
2、请给出下图的邻接矩阵和邻接表，写出从顶点a出发对此图进行深度优先和广度优先进行遍历的顶点序列。

a

 
b
e
d
c
f
 
3、对于下图请画出最小生成树。
 
 
4、已知一表为(49，66，73，52，40，37，65，43)，使按表中元素的次序依次插入一棵初始为空的二叉排序树，画出表中元素构成的二叉排序树。
 
 
 
5、已知一棵三阶的B-树如下图所示，假定依次删除关键字46，24，8，15请画出每次删除结点后树的情况：
6、已知一组关键字为（19，14，23，01，68，20，84，27，55，11,10，79），则按哈希函数H(key)=key MOD 13和线性探测法解决冲突构造这组关键字的哈希表。
 
 
 
7、判断下面的序列是否是堆？如果不是，则把它调整为堆：
（5，56，20，23，40，38，29，61，35，76，28，100）
 
 
五、程序题（共22分）
1、阅读下列算法，并回答下列问题：（4分）
完善程序,并回答该算法完成什么功能？算法中r[n+1]的作用是什么？
void sort (elemtype r[],int n)
{int k,i;
 for(k=n-1;k>=1;k- -)
   if(r[k]>r[k+1])
{ r[n+1]=r[k];
    for(i=k+1;r[i]<r[n+1];i++)
      r[i-1]=r[i];
                       ;}
}}
 
2、完成下列程序,并说出该算法所完成的功能。（8分）
void weizhisort(struct node r[ n],int n)
{ int low,high,mid,j,i;
for(i=2;i<=n;i++)
     { r[0]=r[i];
        low=__________;
        high=_________;
 while(low<=high)
{    mid=(low+high)/2;
     if(r[0].key<r[mid].key)
       _______________;
    else   low=mid+1; }
for(j=i-1;j>=l;j--)
      r[j+1]=r[j];
   r[high+1]=r[0];
       }}
其中数据类型定义为:
struct node
{ int key;
 Infotype otherinfo;
}
 
3、说出下面算法完成的功能。(2分)
void delete( int a[n],int i)
{if (i<0)||(i>=n) printf(“error”);
else
{for (j=i-1;j<n;j++)
a[j]=a[j+1];
   n=n-1;}
   }
 
4、完善程序，说明其功能(8分)
#define NULL 0;
typedef struct Bitnode{
 char data;
 Struct Bitnode *lchild,*rchild;
} Bitreptr;
 
void inorder_notrecursive(Bitreptr bt,Status(Visit)(TelemType e)))
 { InitStack(S);
 P=T;
 while(P||!StackEmpty(s))
 { if (P) {Push(S,P);            ;
else{
__________;
if(!Visit(P->data)) return Error;
            ;
}
}return OK;
}

相关阅读推荐：

› 数据结构期末试卷

› 数据结构 单源最短路径教学设计

[]
分享到：
看过本文的人还看过

说课视频

人教版三年级语文说课稿视频人教版三年级语文说课稿视频 人教版八年级语文下册说课视频人教版八年级语文下册说课视频 人教版英语七年级下册说课视频人教版英语七年级下册说课视频 人教版八年级数学下册说课视频人教版八年级数学下册说课视频

说课下载

说课阅览

说课视频