数据结构_3

6、已知二叉树 T 的先序序列为 abdegcfh，中序序列为 dbgeachf，则 T 的后序序列为（ Ａ、gedhfbca Ｂ、dgebhfca ） 。 7、下列叙述中错误的是（
Ａ、由树的先序遍历序列和后序遍历序列可以惟一确定一棵树 Ｂ、二叉树不同于度为 2 的有序树 Ｃ、深度为 k 的二叉树上最少有 k 个结点 Ｄ、在结点数目相同的二叉树中，最优二叉树的路径长度最短 8、设无向图的顶点个数为 n，则该图最多有（ Ａ、n-1 Ｂ、n(n-1)/2 Ｃ、n(n+1)/2 Ｄ、n ）条边。
3、设广义表 L=((a,()),b,(c,d,e))，则 Head(Tail(Tail(L)))的值为（
Ａ、b
Ｂ、c
Ｃ、(c)
Ｄ、(c,d,e) ） 。
4、下列叙述中错误的是（
Ａ、对数组一般不做插入和删除操作 Ｂ、顺序存储的数组是一个随机存取结构 Ｃ、空的广义表没有表头和表尾 Ｄ、广义表的表尾可能是原子也可能是子表 5、一棵度为 3 的树中，度为 3 的结点有 2 个，度为 2 的结点有 2 个，度为 1 的结点有 2 个，则 度为 0 的结点有（ Ａ、5 个 Ｂ、6 个 ） 。 Ｃ、7 个 Ｄ、8 个 ） 。 Ｃ、abcdefgh Ｄ、acbfedhg
10、设有向图 G 中有五个顶点，各顶点的度分别为 3、2、2、1、2，则 G 中弧数为（ Ｄ、无法确定
二、 （10 分）
设有上三角矩阵(aij)n×n，将其上三角元素逐行存于数组 B[m]中（m 充分大） ，使得 B[k]=aij，求 用 i 和 j 表示 k 的下标变换公式。
三、 （10 分）
设二叉树如下，试对其进行先序线索化，画出相应的先序线索二叉树存储结构示意图。
q=p; p=p->next; //q 指向当前待处理结点，p 指向剩余链表 if (q->data>=’A’ && q->data<=’Z’|| q->data>=’a’ && q->data<=’z’){ q->next=LC->next; LC->next=q; } //字母字符入循环链表 LC q->next=LN->next; LN->next=q; } //数字字符入循环链表 LN q->next=LO->next; LO->next=q; } }//while free(L); }//partition void InitCL(LinkList &L){ //对循环链表进行初始化 L=(LinkList)malloc(sizeof(LNode)); if (!L) exit(OVERFLOW); L->next=L; } //释放单链表 L 的头结点 //其他字符入循环链表 LO else { else if (q->data>=’0’ && q->data<=’9’){
五、设有 AOE 网如下，要求：
⑴求图中各顶点代表的事件的最早发生时间和最晚发生时间； ⑵求图中各弧代表的活动的最早开始时间和最晚开始时间； ⑶列出各条关键路径。
答：
关键路径１：v1→v2→v5→v7 关键路径２：v1→v3→v6→v7
六、设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。 答：
答：
四、设元素的入栈次序为 a、b、c、d，且在入栈的过程中允许出栈，试写出所有不可能得到
的出栈序列。
答：
dabc dacb dbac dbca dcab cadb cabd cdab bdac adbc
五、设 a='data structure'，b='computer'，c='demo'，试求：
Status LevelOrderTraverse(Bitree T,Status (*visit)(TElemType e)){ if (!T) return OK; InitQueue(Q); EnQueue(Q,T); DeQueue(Q,p); //空二叉树 //访问根结点 //初始化辅助队列 //指向结点的指针入队 //若队列非空 //队头指针出队
六、已知单链表 L 中含有三类字符的数据元素，即字母字符、数字字符和其他字符，试编写算
法将 L 分割为三个循环链表，其中每个循环链表只含一类字符。
答：
void partition(LinkList &L,LinkList &LC,LinkList &LN,LinkList &LO){ //L 带头结点，LC 为含字母字符的循环链表，LN 为含数字字符的循环链表， //LO 为含其他字符的循环链表 InitCL(LC); InitCL(LN); InitCL(LO); p=L->next; while (p){ //对三个循环链表进行初始化 //p 指向第一个结点
答：
四、设用于通信的电文由 8 个字母组成，字母在电文中出现的频率分别为 0.12、0.31、0.22、
0.02、0.03、0.08、0.17、0.05。试为这 8 个字母设计哈夫曼编码，要求画出设计过程中所构 造的哈夫曼二叉树。
答：
编码：
0.02: 00100 0.03: 00101 0.05: 0011 0.08: 000 0.12: 100 0.17: 101 0.22: 01 0.31: 11
if (!visit(T->data)) return ERROR; while (!QueueEmpty(Q)){
if (p->lchild){//先访问 p 所指结点的左孩子，再访问其右孩子 if (!visit(p->lchild->data)) return ERROR; EnQueue(Q,p->lchild); }//if if (p->rchild){ if (!visit(p->rchild->data)) return ERROR; EnQueue(Q,p->rchild); }//if }//while return OK; }//LevelOrderTraverse
六、 （20 分）
设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。
答案：
一、选择题
C、B、D、D、C、B、D、B、D、B
二、 设有上三角矩阵(aij)n×n， 将其上三角元素逐行存于数组 B[m]中 （m 充分大） ， 使得 B[k]公式。
答： i ( 2n i 1) k j 2 三、设二叉树如下，试对其进行先序线索化，画出相应的先序线索二叉树存储结构示意图。
for (i=1;i<=n;i++) for (j=1;j<=i;j++) for (k=1;k<=n;k++) x++;
答：
n 2 (n 1) 2
三、设单链表Ｌ如图所示：
画出执行如下程序段后，各指针变量及单链表Ｌ的示意图。 p=L; for(i=1;i<=3;i++){ q=(LinkList)malloc(sizeof(LNode)); q->data=i*3; q->next=p->next; p->next=q; }
《数据结构》
一、选择题（每题 3 分，共 30 分）
1、在树形结构中，数据元素间存在（）的关系。 Ａ、一对一 Ｂ、一对多 Ｃ、多对多 Ｄ、除同属一个集合外别无关系 2、下列说法中错误的是（） 。 Ａ、数据对象是数据的子集 Ｂ、数据元素间关系在计算机中的映象即为数据的存储结构 Ｃ、非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系 Ｄ、抽象数据类型指一个数学模型及定义在该模型上的一组操作 3、下列不属算法特性的是（） 。 Ａ、有穷性 Ａ、n Ｂ、确定性 Ｃ、零或多个输入 Ｄ、健壮性 4、在长为 n 的顺序表中删除一个数据元素，平均需移动（）个数据元素。 Ｂ、n-1 Ｃ、n/2 Ｄ、(n-1)/2 5、 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算， 则利用 （）存储方式最节省时间。 Ａ、顺序表 Ｂ、双链表 Ｃ、带头结点的双向循环链表 Ｄ、单循环链表 6、在一个可存放 n 个数据元素的顺序栈中，假设以高地址端为栈底，以 top 为栈顶指针，当向 栈中压入一个数据元素时，top 的变化是（） 。 Ａ、不变 Ｂ、top=n Ｃ、top++ Ｄ、top-7、设在一不带头结点的链队列中，front 和 rear 分别为其队头和队尾指针，则删除一个结点 的操作是（） 。 Ａ、 rear=front->next Ａ、S Ｂ、S->next Ｂ、 rear=rear->next Ｃ、S->next==NULL Ｃ、 front=front->next Ｄ、 front=rear->next 8、判定一个栈顶指针为 S 且不带头结点的链栈为空栈的条件是（） 。 Ｄ、!S 9、设在一不带头结点的链队列中，front 和 rear 分别为其队头和队尾指针，则判定该队中只 有一个结点的条件是（） 。 Ａ、front->next Ｂ、rear->next 10、串的长度是指（） 。 A、串中所含不同字母的个数 C、串中所含不同字符的个数 B、串中所含字符的个数 D、串中所含非空格字符的个数 Ｃ、front==rear Ｄ、front!=rear
六、 （20 分）
已知单链表 L 中含有三类字符的数据元素，即字母字符、数字字符和其他字符，试编写算法将 L 分割为三个循环链表，其中每个循环链表只含一类字符。
答案
一、选择题
1、B 2、B 3、D 4、D 5、A 6、D 7、C 8、D 9、C 10、B
二、设ｎ为正整数，试确定如下程序段中语句“x++;”的频度。