数据结构10级A1-试卷

PAGEPAGE8天津工业大学计算机科学与软件学院一、单项选择：（每题2分，共13题，共26分）（说明：将答案字母填写在答题纸中）分数1、从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2、线性表是具有n个（）的有限序列（n>0）。A．表元素B．字符C．数据元素D．数据项3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表4、若长度为n的线性表采用顺序存储结构，在其第i个位置（1<=i<=n）插入一个新元素的算法的时间复杂度是…………………………（）A．O(0)B．O(1)C．O(n)D．O(n2)5、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i6、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为。（）A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m7、在一个单链表中，已知q所指结点是p所指结点的前趋结点，若在q和p之间插入S结点，则需执行……………………………………（）A．p->next=S;S->next=q;B．q->next=S;S->next=p;C．S->next=p->next;p->next=S;D．p->next=S->next;S->next=p;8、若让元素1,2,3依次进栈，则出栈次序不可能出现()种情况。A.3,2,1B.2,1,3C.3,1,2D.1,3,29、在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④10、利用二叉链表存储树，则根结点的右指针是（）。A．指向最左孩子B．指向最右孩子C．空D．非空11、广义表运算式Tail(c,d)的操作结果是（）。A.(c,d)B.c,dC.((c,d))D.(d)12、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树的根是（）：A．EB.F　C.G　D.H13、设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0二、填空题：（每空1分，共14空，共14分）（说明：将答案填写在答题纸中）分数1、数据结构中其逻辑结构有（1），（2），（3），（4）四种。2、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用(5)存储结构。3、顺序存储结构是通过(6)表示元素之间的关系的;链式存储结构是通过(7)表示元素之间的关系的。4、数组A[5][6]的每个元素占五个字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素A[4][5]的地址是(8)。5、深度为k的完全二叉树至少有(9)个结点，至多有(10)个结点。6、AOV网中,结点表示(11),边表示(12)。AOE网中,结点表示(13),边表示(14)。三、作图题：（每题5分，共3题，共15分）（说明：将答案填写在题后空白处）分数一森林如下图所示，请将该森林转换为相对应的二叉树。DBAOECpF2、已知一个无向图如下图所示，要求用Kruskal算法生成最小树（试画出构造过程）。12654320101166181014593、已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg,请画出对应的二叉树。四、应用题：（1，2，4题各10分，3题8分，共4题，共38分）（说明：将答案填写在题后空白处）分数1、给出图G：（1）．画出G的邻接表表示图；（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。367589421有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试画出对应的哈夫曼树,并为这6个字母哈夫曼编码。(要求左子树的权值小于右子树的权值)3、给出一组关键字T=(25,84,21,46,13,27,68,35,20),写出用下列算法从小到大排序时第一趟结束时的序列；(1)希尔排序（第一趟排序的增量为5）(2)快速排序（选第一个记录为枢轴（分隔））4、设有一项，建立如图所示的AOE网络，以v1为源点,以v5为终点，试回答以下问题：（10分）（1）写出全部拓扑排序（2）每一事件的最早发生时间和最迟发生时间。（3）每一活动的最早开始时间和最迟开始时间。（4）画出这个AOE网络的关键路径。93V3V5V132245V6V4V2五、算法题：（此题7分）（说明：将答案填写在题后空白处）分数输入50个学生的记录（每个学生的记录包括学号和成绩），组成记录数组，采用选择排序排序,把下面的程序补充完整。main（）{STUDENTstuScore[50]；Input(stuScore,50);Sort（stuScore,50）；}typedefstructNode{intnNo;//学号floatfScore;//成绩}STUDENT；voidInput(STUDENT*pStuintnStuNum){...}voidSort（STUDENT*pStu,intnStuNum）{…}天津工业大学计算机科学与软件学院答案与评分标准一、单项选择题：（每题2分，共13题，共26分）（说明：将答案字母填写在答题纸中）分数12345CCDCB678910ABCDC111213DAB二、填空题：（每空1分，共14空，共14分）（说明：将答案填写在答题纸中）分数12345线性结构树形结构图或网状结构集合机构顺序678910存储位置指针或地址114511121314活动活动间优先关系事件活动三、作图题：（每题5分，共3题，共15分）（说明：将答案填写在题后空白处）分数一森林如下图所示，请将该森林转换为相对应的二叉树。EDBACOpEDBACOpFF【评分标准：根节点错扣一分，其余节点错扣0.5分】已知一个无向图如下图所示，要求用Kruskal算法生成最小树（试画出构造过程）。12654320101166181014591265435612654351265435611126543561191265435611910【评分标准：每错一步扣1分】已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg,请画出对应的二叉树。【评分标准：树的根错扣1分，左子树错扣2分，右子树错扣2分】四、应用题：（1，2，4题各10分，3题8分，共4题，共38分）（说明：将答案填写在题后空白处）分数1、给出图G：（1）．画出G的邻接表表示图；（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。367589421【评分标准：答案不唯一，邻接表4分，广度优先3分，深度优先3分】有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试画出对应的哈夫曼树,并为这6个字母设计哈夫曼编码。(要求左子树的权值小于右子树的权值)【评分标准：画图4分，每个字符的哈夫曼编码1分】3、给出一组关键字T=(25,84,21,46,13,27,68,35,20),写出用下列算法从小到大排序时第一趟结束时的序列；(1)希尔排序（第一趟排序的增量为5）(2)快速排序（选第一个记录为枢轴（分隔））（1）希尔排序：25，68，21，20，13，27，84，35，46（2）快速排序：20，13，21，25，46，27，68，35，84【评分标准：每个排序4分】4、设有一项工程，建立如图所示的AOE网络，以v1为源点,以v5为终点，试回答以下问题：（10分）（1）写出全部拓扑排序（2）每一事件的最早发生时间和最迟发生时间。（3）每一活动的最早开始时间和最迟开始时间。（4）画出这个AOE网络的关键路径。93V3V5V132245V6V4V2【评分标准：（1）2分，（2）、（3）各3分，（4）2分】五、算法题：（此题7分）（说明：将答案填写在题后空白处）分数输入50个学生的记录（每个学生的记录包括学号和成绩），组成记录数组，采用选择排序方法排序,把下面的程序补充完整。main（）{STUDENTstuScore[50]；Input(stuScore,50);Sort（stuScore,50）；}typedefstructNode{intnNo;//学号floatfScore;//成绩}STUDENT；voidInput(STUDENT*pStuintnStuNum){答案略}voidSort（STUDENT*pStu,intnStuNum）{答案略}