}ຫໍສະໝຸດ 解：4七．程序设计题
试写一个算法判别读入的一个以‘#’为结束符的字符序列是否是“回文”。 （允许直接使用建栈、建队、判栈空、判队空等函数） 解： int PalindromeTest() // 判别输入的字符串是否回文序 列,是则返回1,否则返回0 { InitStack(S);InitQueue(Q); while((c=getchar())!='#') { Push(S,c);InQueue(Q,c); // 同时使用栈和队列两种结构 } while(!StackEmpty(S)) { Pop (S,a);OutQueue (Q,b)); if (a!=b) return ERROR; } return OK; }
{
int ldep,rdep; if(T==NULL) return 0; else { ldep= BTD (T->lchild) ; rdep= BTD (T->rchild) ; if(ldep>rdep) return ldep+1; else return rdep+1; } 求二叉树深度
A BA D E C F G H I
A． A、B、C、D、E、F、G 、H、I B． A、B、D、H、I、E、C、F、G C． H、D、I、B、E、A、F、C、G
D． H、I、D、E、B、F、G、C、A 13．最小生成树的构造可使用（ A ）算法。 A．prim算法 B．卡尔算法 法 D．迪杰斯特拉算法 14．在下列图中，度为3的结点是（ B ）。
六．按题目要求，写出运行下列程序的结果
二叉树的结构如图所示，试写出执行下列算法后的输出结果： 。 typedef struct BT { datatype data; // 定义结点 C F BD A D G E BT *lchild; BT *rchild; }BT; int BTD(BT *T)
点。 15．在分块查找方法中，首先查找 索引 ，然后再查找相应的块。 16．哈希表是按 散列 存储方式构造的存储结构。 17．对于大文件的排序要研究在外存上的排序技术，这种排序称为 外 排序 。 18．两个序列分别为： L1={25，57，48，37，92，86，12，33} L2={25，37，33，12，48，57，86，92}。 用冒泡排序法对L1和L2进行排序，交换次数较少的是序列： L2 。 19．无向图的邻接矩阵 一定是 对称矩阵。 20．在一棵二叉树中，度为2 的结点有5 个，度为1 的结点有6 个，则叶 子结点数有 6 个。
seqstack *s; 则顺序栈s栈满的条件是​ ( C )。 A．s->top<>0 B．s->top==maxsize C．s->top==maxsize-1 D．s->top!=maxsize 6．经过下列栈的运算后，SEmpty(s)的值是（ C ）。 InitStack(s)（初始化栈）;Push(s,a); Push(s,b);Pop(s,x); Pop(s,x); A．a B．b C．1 D．0 7．一个循环队列一旦说明，其占用空间的大小（ A ）。 A．已固定 B．可以变动 C ．不能固定 D．动态变化 8．当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元 素的下标为（ B ）。 A．n-2 B．n-1 C ．n D．n+1 9．某串的长度小于一个常数，则采用（ B ）存储方式最节省空间。 A．链式 B ．顺序 C．堆结构 D．无 法确定 10. S="Today is 30 July 2005"，LenStr(S)=( D )。 A．18 B ．19 C ．20 D．21 11．A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是 （ C ）。 A．A在B右方 B．A是B祖先 C．A在B左方 D．A是B子孙 12．如右图所示的二叉树，后序遍历的序列是（ D ）
解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL＝（4 ＋5＋3）×2＋（1＋2）×3=33 (15) (9) (6) 4 5 3 (3) 1 2
四．应用题
1． 根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。 F=（D，R），其中： D={50，25，64，57，82，36，75，55}， R={<50,25>,<50,64>,<25,36>,<64,57>, <64,82>,<57,55>,<57,75>} 解： 25 50 75 57 36 82 64 55
C E F I
其后序遍历的序列为：G H D B E I F C A 4． 已知一个无向图的顶点集为：{a，b，c，d，e}，其邻接矩阵如 下： （1） 画出该图的图形； （2） 写出从顶点a出发按深度优先搜索进行遍历的结点序列。
解： （1）
（2）深度优先搜索： a c b e d a b d c e （或a b d e c）
三．选择题
1．以下任何两个结点之间都没有逻辑关系的是（ D ） A. 图型结构 B. 线性结构 C. 树型结构 D. 集合 2．链接存储的存储结构所占存储空间（ A ）。 A． 分两部分，一部分存放结点的值，另一部分存放表示结点间关 系的指针 B． 只有一部分，存放结点值 C． 只有一部分，存储表示结点间关系的指针 D． 分两部分，一部分存放结点值，另一部分存放结点所占单元素 3．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5 个元素的地址是（ B ） A．110 B．108 C．100 D．120 4．两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元 素前驱的条件是（ ）。 A．P->next= =Q->next B．P->next= = Q C．Q->next= = P D．P= = Q 5．顺序栈的类型定义如下： typedef maxsize 64; typedef struct {int data[maxsize]; int top; }seqstack;
的正确性
// 插入结点函数
//
检查插入位置
{ cout<< " 位置出错！"; return(0);} for (j=L->last; j>=i-1 ; j--) // 结点移动 L->data[j+1]=L->data[j] ; L->Lata[i-1]= x ; // 新结点插入 L->last ++ ; （或L->last= L->last +1） return(1); }
属于树结构 2． 把下列森林转换为二叉树 F A G H I C D B
K E J
解： K A B C H DD F G E I J
3． 已知一棵二叉树的先序遍历序列为：ABDGHCEFI，中序遍历序列 为：GDHBAECIF，试恢复该二叉树，并写出它的后序遍历的序列。 答：恢复的二叉树为： G H A B D
封装在一个结构体
// 将data和last
int last; }SeqList; int InsList(SeqList *L,int i,datatype x) { int j; if (L->last= =MAXLEN-1) { cout<< " 顺序表已满！"; return(-1);} if( i<1 || i>L->last+2 )
二．填空题
1．在图形结构中，每个结点的前趋结点可以有 多个 ，后继结点可 以有多个。 2．数据结构主要研究数据的逻辑结构、 存储结构 和算法。 3．采用 顺序 存储结构的线性表叫顺序表。 4．在双链表中要删除已知结点*P，其时间复杂度为 O (1) 。 5．在出栈操作中，要先判断栈是否为空，否则会出现 下溢 现象。 6．链栈LS，指向栈顶元素的指针是 LS->next 。 7．在队列中存取数据应遵从的原则是 先进先出 。 8．设长度为n的链队列用单循环链表表示，若只设头指针，则入队操 作的时间复杂度为 O（n）。 9．串链接序存储的优点是插入、删除方便，缺点的 空间利用率 低 。 10．所有模式匹配不成功的起始位置称为： 无效位移 。 11．有20个结点的完全二叉树，编号为10的结点的父结点的编号是 5 。 12．由树转换成二叉树时，其根结点没有 右子树 。 13．图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。 14．对n个顶点，e条弧的有向图，其邻接表表示中，需要 n+e 个结
1 2 3 4 5
C．哈夫曼算
A．V1
B. V2
C.
V3 D. V4
15．动态查找的全部运算是（ D ）。 A．初始化 B. 插入、删除 C．建表、查表和读表元 D．前三项中的全部 16．下列（ C ）不是利用查找表中数据元素的关系进行查找的方法。 A．平衡二叉树 B．有序表的查找 C. 散列查找 D．二叉排序树的查 找 17．稳定的排序方法是指在排序前后，关键字值相等的不同记录间的前 后相对位置（ B ）。 A．保持相反 B．保持不变 C．不定 D． 无关 18．下述几种排序方法中，要求内存量最大的是：（ D ）。 A．插入排序 B．选择排序 C．快速排序 D. 归并排序 19．已知一个算术表达式的中缀表达式为：A+B*C-D/E，后缀表达式为 （ B ）。 A．AB+C*DE-/ B． ABC*+DE/C． ABC*+D/ED． ABC*+DE-/ 20．【计算机研2001】用5个权值{3, 2, 4, 5, 1}构造的哈夫曼 （Huffman）树的带权路径长度是（ B ）。 Ａ．32 Ｂ．33 Ｃ．34 Ｄ．15
5． 对于给定结点的关键字集合K={15，9，20，12，17，4，18，10， 29，6}，构成一棵二叉排序树，并写出该二叉排序树中序遍历的结点序