数据结构试题及答案
一．是非题（每题1分共10分）
1. 线性表的链式存储结构优于顺序存储结构。F
2. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。F
先序中序后序遍历二叉树3．字符串是数据对象特定的线性表。T
4．在单链表P指针所指结点之后插入S结点的操作是：P->next= S ; S-> next = P->next; F
5．一个无向图的连通分量是其极大的连通子图。T
6．邻接表可以表示有向图，也可以表示无向图。T
7．假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的中序遍历。T
8．通常，二叉树的第i层上有2i-1个结点。F
9．对于一棵m阶的B-树，树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有ém/2ù个关键字。F
10．对于任何待排序序列来说，快速排序均快于起泡排序。F 二．选择题（每题2分共28分）
1．在下列排序方法中，（c ）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（  d ）方法所有情况下时间复杂度均为0(nlogn)。
a. 插入排序
b. 希尔排序
c. 快速排序
d. 堆排序
2. 在有n个结点的二叉树的二叉链表表示中，空指针数为（b ）。
a.不定
b.n+1
c.n
d.n-1
3. 下列二叉树中，（a ）可用于实现符号不等长高效编码。
a.最优二叉树
b.次优查树
c.二叉平衡树
d.二叉排序树
4. 下列查方法中，（a ）适用于查有序单链表。
a.顺序查
b.二分查
c.分块查
d.哈希查
5. 在顺序表查中，为避免查过程中每一步都检测整个表是否查完毕，可采用（a ）方法。
a.设置监视哨
b.链表存贮
c.二分查
d.快速查
6. 在下列数据结构中，（  c ）具有先进先出特性，（  b ）具有先进后出特性。
a．线性表b．栈c．队列d．广义表
7．具有m个结点的二叉排序树，其最大深度为（f ），最小深度为（b ）。
a. log 2 m
b. └ log2 m ┘ +1
c. m/2
d .┌ m/2 ┐ -1    e. ┌ m/2 ┐    f. m
8．已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。
下列选择中（c ）是快速排序一趟排序的结果。
（b ）是希尔排序（初始步长为4）一趟排序的结果。
（d ）是基数排序一趟排序的结果。
（a ）是初始堆（大堆顶）。
a. 84，79，64，37，57，52，58，26，28，34，56。
b. 28，34，57，26，56，52，58，37，79，84，64。
c. 28，34，37，26，52，56，64，79，58，84，57。
d. 52，34，64，84，56，26，37，57，58，28，79。
e. 34，56，26，58，52，64，37，28，79，57，84。
f. 34，56，26，58，52，79，37，64，28，84，57。
三．填空题（每题2分共20分）
1．有向图的存储结构有（邻接矩阵）、（邻接表）、（十字链表）等方法。
2．已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。其后序遍历次序为（edcgbfa）。层次遍历次序为（afbcgde）。
3．设有二维数组A 5 x 7 ，每一元素用相邻的4个字节存储，存储器按字节编址。已知A00的存储地址为100。则按行存储时，元素A14的第一个字节的地址是（144）；按列存储时，元素A14的第一个字节的地址是（184）。
4．请在下划线上填入适当的语句，完成以下法算。
Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)){
//先序非递归遍历二叉树。
Initstack ( S ); Push ( S,T );
While ( !stackempty( S ) )
{ While ( gettop( S, p )&& p ) { visit (p->data ) ; push(S, p->lchild ;}
Pop ( S , p );
If ( !stackempty(s) ) { pop(S, p) ; push( S, p->rchild ); }
}
return ok;
四、算法设计题（共17分）
1. 单链表结点的类型定义如下：
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *Linklist;
写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。(注：不破坏A和B的原有结构.)
Merge (Linklist A, Linklist B, Linklist &C )
void Merge ( Linklist A, Linklist B, Linklist &C)
{ C=(Linklist)malloc(sizeof(LNode));
pa=A->next; pb=B->next; pc=C;
while(pa&&pb){
pc->next=(Linklist)malloc(sizeof(LNode)); pc=pc->next;
if(pa->data<=pb->data){
pc->data=pa->data; pa=pa->next; }
else{
pc->data=pb->data; pb=pb->next; } }
if(!pa) pa=pb;
while(pa){
pc->next=(Linklist)malloc(sizeof(LNode));
pc=pc->next; pc->data=pa->data; pa=pa->next; } pc->next=NULL; }
2. 二叉树用二叉链表存储表示。typedef struct BiTNode {
TelemType data;
Struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
编写一个复制一棵二叉树的递归算法。
BiTree CopyTree(BiTree T) {
if (!T ) return NULL;
if (!(newT = (BiTNode*)malloc(sizeof(BiTNode) ) ) )
exit(Overflow);
newT-> data = T-> data;
newT-> lchild = CopyTree(T-> lchild);
newT-> rchild = CopyTree(T-> rchild);
return newT; }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。