数据结构期末考试试题及答案 关于外汇期货的知识有哪些问题及答案解析视频

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

一.是非题(每题1分共10分 线性表的链式存储结构优于顺序存储结构。F栈和队列也是线性表。如果需要,可对它们中的任一元素进行操作。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;

四.简答题(每题5分共25分

1.将图示森林转换为二叉树,并对该二叉树中序全序线索化。 2.已知Hash函数为H(K=K mod 13 ,散列地址为0 --14, 用二次探测再散列处理冲突,给出关键字(23,34,56, 24,75,12,49, 52,36,92,06,55在散列 地址的分布。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 3. 右图为一棵3阶 B 树。(20,25 a. 画出在该树上插入元素15后的 B 树。/│ b. 接着,再删除元素35,画出删除后的B 树。(10,14 (21(35 4.已知某无向图的邻接表存储结构如图所示。 a.请画出该图。 b.根据存储结构给出其深度优先遍历序列及广度优先遍历序列。 c.画出其深度优先生成树及广度优先生成树。 0 a 2 4 / 1 b 2 3 4 / 2 c 0 1 4 / 3 d 1 / 4 e 0 1 2 / 5. 设在某通信系统中使用了八个字符,它们出现的频率分别为0.08,0.05,0.1,0.12,0.26,0.18,0.14,0.07,试构造一棵赫夫曼树,并给出赫夫曼编码。

五.算法设计题(共17分 单链表结点的类型定义如下: 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=(Linklistmalloc(sizeof(LNode; pa=A->next; pb=B->next; pc=C; while(pa&&pb { pc->next=(Linklistmalloc(sizeof(LNode; pc=pc->next; if(pa->datadata { pc->data=pa->data; pa=pa->next;} else { pc->data=pb->data; pb=pb->next;} } if(!pa pa=pb; while(pa { pc->next=(Linklistmalloc(sizeof(LNode; pc=pc->next; pc->data=pa->data; pa=pa->next; } pc->next=NULL; }二叉树用二叉链表存储表示。 typedef struct BiTNode { TelemType data; Struct BiTNode *lchild, *rchild; } BiTNode, BiTree; 编写一个复制一棵二叉树的递归算法。BiTree CopyTree(BiTree T { if (!T return NULL; if (!(newT = (BiTNodemalloc(sizeof(BiTNode exit(Overflow; newT-> data = T-> data; newT-> lchild = CopyTree(T-> lchild; newT-> rchild = CopyTree(T-> rchild; return newT;