搜索
数据结构模拟试题...一、简答题（15分，每小题3分）1.简要说明算法与程序的区别。2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？3.说明在图的遍历中，设置访问标志数组的作用。4.说明以下三个概念的关系：头指针，头结点，首元素结点。5.在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？二、判断题（10分，每小题1分）正确在括号内打√，错误打×()（1）广义表(((a),b),c)的表头是((a),b)，表尾是(c)。()（2）在哈夫曼树中，权值最小的结点离根结点最近。()（3）基数排序是高位优先排序法。()（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。()（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p-next=s;s-next=p-next;()（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。()（7）数组元素的下标值越大，存取时间越长。()（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。()（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。()（10）长度为1的串等价于一个字符型常量。三、单项选择题（10分,每小题1分）1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？A、堆排序B、直接插入排序C、快速排序D、冒泡排序2．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：A）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元素全部置为0C）将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素全部置为03．有一个含头结点的双向循环链表，头指针为head,则其为空的条件是：A.head-priro==NULLB.head-next==NULLC.head-next==headD.head-next-priro==NULL4.在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找关键码值11，所需的关键码比较次数为：A)2B)3C)4D)55.以下哪一个不是队列的基本运算？A）从队尾插入一个新元素B）从队列中删除第i个元素C）判断一个队列是否为空D）读取队头元素的值6.在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为：A)n–i+1B)n–iC)iD)i–17．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为:A)顺序表B)用头指针表示的循环单链表C)用尾指针表示的循环单链表D)单链表8．对包含n个元素的哈希表进行查找，平均查找长度为：A)O(log2n)B)O(n)C)O(nlog2n)D)不直接依赖于n9．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：A、48B、49C、50D、5110．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：A）3B）2C）4D）5四、填空题（10分，每空1分）1．填空完成下面一趟快速排序算法：intQKPass(RecordTyper[],intlow，inthigh){x=r[low]；while(lowhigh){while(lowhigh&&r[].key=x.key)high--；if(lowhigh){r[]=r[high]；low++;}while(lowhigh&&r[].keyx.key)low++;if(lowhigh){r[]=r[low]；high--;}}r[low]=x；returnlow;}2.假设用循环单链表实现队列，若队列非空，且队尾指针为R,则将新结点S加入队列时，需执行下面语句：；；R=S；3．通常是以算法执行所耗费的和所占用的来判断一个算法的优劣。4．已知一个3行、4列的二维数组A（各维下标均从1开始），如果按“以列为主”的顺序存储，则排在第8个位置的元素是：5．高度为h的完全二叉树最少有个结点。五、构造题（20分）1．（4分）已知数据结构DS的定义如下，请给出其逻辑结构图示。DS=(D,R)D={a,b,c,d,e,f,g}R={T}T={a,b,a,g,b,g,c,b,d,c,d,f,e,d,f,a,f,e,g,c,g,d,g,f}2．（6分）对以下关键字序列建立哈希表：（SUN,MON,TUE,WED,THU,FRI,SAT）,哈希函数为H(K)=（K中最后一个字母在字母表中的序号）MOD7。用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并计算出在等概率情况下查找成功的平均查找长度。3.（6分）将关键字序列（3，26，12，61，38，40，97，75，53，87）调整为大根堆。4．（4分）已知权值集合为：{5，7，2，3，6，9}，要求给出哈夫曼树，并计算其带权路径长度WPL。六、算法分析题（10分）阅读下面程序，并回答有关问题。其中BSTree为用二叉链表表示的二叉排序树类型。（1）简要说明程序功能。（5分）（2）n个结点的满二叉树的深度h是多少？（3分）（3）假设二叉排序树*bst是有n个结点的满二叉树,给出算法的时间复杂度。（2分）intProc(BSTree*bst,KeyTypeK){BSTreef,q,s;s=(BSTree)malloc(sizeof(BSTNode));s-key=K;s-lchild=NULL;s-rchild=NULL;if(*bst==NULL){*bst=s;return1;}f=NULL;q=*bst;while(q!=NULL){if(Kq-key){f=q;q=q-lchild;}else{f=q;q=q-rchild;}}if(Kf-key)f-lchild=s;elsef-rchild=s;return1;}七、算法设计题（25分）1．已知一个带头结点的整数单链表L，要求将其拆分为一个正整数单链表L1和一个负整数单链表L2。（9分）2．无向图采用邻接表存储结构，编写算法输出图中各连通分量的结点序列。（8分）3．编写一个建立二叉树的算法，要求采用二叉链表存储结构。（8分）2002级《数据结构》试卷参考答案与评分标准一、简答题（15分，每小题3分）6.算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。7.主要与哈希函数、装填因子α有关。如果用哈希函数计算的地址分布均匀，则冲突的可能性较小，如果装填因子α较小，则哈希表较稀疏，发生冲突的可能性较小。8.图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结点。9.头指针指向头结点，头结点的后继域指向首元素结点。10.当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因此叫假溢出。解决的方法是采用循环队列，即令最后一个单元的后继是第一个单元。二、判断题（10分，每小题1分）（1）(√)（2）(×)（3）(×)（4）(√)（5）(×)（6）(√)（7）(×)（8）(√)（9）(×)（10）(×)三、单项选择题（10分,每小题1分）1．D）2．B）3．C）4.C）5.B）6.A)7．C)8．D)9．C）10．C）四、填空题（10分，每空1分）1．highlowlowhigh2.S-next=R-next；R-next=S；3．时间空间4．A[2,3]5．2h-1五、构造题（20分）1．（4分）2．（6分）ASLsucc=(1×4+2×2+3)/7=11/7SUNMONTHUFRIWEDTUESAT01234567893.（6分）4．（4分）已知权值集合为：{5，7，2，3，6，9}，要求给出哈夫曼树，并计算其带权路径长度WPL。WPL=2×(9+6+7)+3×5+4×(2+3)=79六、算法分析题（10分）解：（1）在二叉排序树中插入关键字为K的结点（2）h=log2(n+1)或h=[log2n]+1（方括号表示向下取整）（3）O(log2(n+1))或O(log2n)七、算法设计题（25分）（答案略）