计算机软件技术基础试卷1.pdf

1、考试中心填写：考试中心填写：湖湖 南南 大大 学学 课课 程程 考考 试试 试试 卷卷 课程名称：数据结构 ；试卷编号：01 ；考试时间：120 分分钟钟年 月 日 考 试 用（请将所有答案写在答题纸上）一、填空题。（20 分）1.已知单链表中指针 q 所指结点是指针 p 所指结点的直接前驱，若在*q 与*p 之间插入*s，则应执行（）语句。2.将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（）。3.堆栈的特点是（）。4.已知完全二叉树的第 5 层有 4 个结点(根结点在第 1 层),则其叶结点数是（）。5.在有n个叶结点的 Huffman 树中,共有（）个结点。6.若 数

2、 据 表 中 每 个 元 素 已 距 其 最 终 位 置 不 远,则 采 用（）算法最省时间。7.内部排序问题的时间复杂度的下限是（）。8.对线性表进行折半查找时性能要能达到 O(logn)，要求线性表必须（）。9.如果具有n个顶点的图是一个环,则它有（）棵生成树。10.具有 n 个顶点的无向图最多有（）条边。二、请将下面的算法填写完整。（10 分）下面算法的功能是：用基数排序法对 n 个无符号整数进行排序（递增），在算法空缺处填上适当语句或表达式，使得算法完整且正确。template void radix(elem a,elem b,int n,int k,int r,int cnt)/k

3、为排序码的个数，r 为基数 int i,j,x,m=1;for(i=1;i=k;i+)/分别对第 i 个排序码进行分配 for(j=0;jr;j+)cntj=0;/初始计数器为 0 for(j=0;jn;j+)装订线（答题不得超过此线）学号：姓名：4、设一个散列表包含 13 个表项,.其下标从 0 到 12,采用线性探查法解决冲突（p（K，i)i），请按以下要求,将下列关键码按从左到右的顺序散列到表中。10，100，32，45，58，126，3，29，200，400，0 散列函数采用除留余数法,用%SIZE（对表长取余运算）将各关键码映像到表中.，请指出每一个产生冲突的关键码可能产生多少次冲突

4、？5、一棵前序序列为 1，2，3，4 的二叉树，其中序序列可能是 4，1，2，3 吗，为什么？设一棵二叉树的前序序列为 1，2，3，4，5，6，7，8，9，其中序序列为 2，3，1，5，4，7，8，6，9，试画出该二叉树。6、假设用于通信的电文由字符集a,b,c,d,e,f,g中的字母构成。它们在电文中出现的幅度分别为0.31,0.16,0.10,0.08,0.11,0.20,0.04,为这 7 个字母统计哈夫曼编码，并计算其平均编码长度。7、插入排序是否为稳定的排序算法？为什么？插入排序在最佳情况和最坏情况下，比较次数和移动数据次数分别为多少？（假设共有 n 个元素）四、算法设计。（35 分

5、）1设某带头结点的单链表 L，,结点中的元素为整型数据，试编写算法，判断该单链表 L中的元素，是否成等差关系，即各元素植依次为a1,a2,a3,a4,an判断ai+1-ai=ai-ai1是否成立，其中 i 满足 1=i=n-1 2设一棵二叉树，结点结构为|lchild|data|rchild 其中 data 域中存放一个字符，设计一个算法按前叙遍历顺序，仅打印出 data 域为数字的字符（即0=datalink=s;s-link=p;(两个先后没有关系;link 写成 next 也可以)2、1 3、后进先出（或 LIFO、先进后出）4、10 5、2n-1 6、插入排序 7、(n log n)（

6、或 n log n)）8、按关键码的值大小有序 9、n 10、n（n1）/2 二、程序填空题（10 分）1、-cnt(aj/m)%r (3 分)2、aj=bj (4 分)3、m*r (3 分)三、应用题（每小题 5 分，共 35 分）1、使用一个数组来存储两个栈，每个栈从各自的端点向中间延伸，从而减少空间的浪费。（3 分），当两个栈顶指针相遇时（|top2top1|1），栈满（1 分）；当栈顶指针为1 或 n时，栈空（1 分）。（数组下标从 0 到 n1）2、二叉查找树如下：（4 分）464588397010110586634 平均查找长度（1122334252）/103.2 （1 分）3、广

7、度优先搜索生成树（1 为起点）（2.5 分）12435 深度优先搜索生成树（2 为起点）（2.5 分）12435 4、下标 0 1 2 3 4 5 6 7 8 9 10 11 12 散列表 0 3 29 200 32 45 58 100 10 126 400 冲突 次数 1 1 2 2 2 散列表(3 分)，冲突次数（2 分）5、（1）不可能。（1 分）反证法证明：假设存在这棵二叉树，则从前序序列可知，1 为二叉树的根节点。同时，从中序序列可知，节点 4 位于该二叉树的左子树，节点 2、3 位于右子树。对于这样一棵二叉树，按照前序遍历的规则，在其前序遍历序列中，节点 4 应该位于节点 2、3

8、之前，这与已知相矛盾。因此，这棵二叉树不存在。（2 分）（2）（2 分）123456798 6、（参考）哈夫曼树如下：（2 分）10.410.590.200.210.100.110.280.310.120.160.040.08fabcdeg 哈夫曼编码分别为：（2 分）a b c d e f g 11 101 011 1001 011 00 1000 平均编码长度20.3130.1630.1040.0830.1120.2040.042.61 （1 分）7、插入排序是稳定的排序算法（1 分），因为排序过程是建立在相邻元素比较的基础之上的（2分）。最佳情况下，需要进行 n1 次比较，移动 0 次元

9、素（1 分）；最差情况下，需要比较 n（n1）/2 次，移动元素 n（n1）/2 次（1 分）。四、算法设计（共 35 分）1、(10 分)typedef struct ListNode int data;Struct ListNode*next;ListNode;BOOL CheckList(ListNode*L)ListNode*a,*pa,*qa;qa=L-next-next;a=L-next;pa=L;if(pa=NULL)|(a=NULL)|(qa=NULL)return false;while(qa!=NULL)if(qa-data+pa-data)!=(2*a-data)retu

10、rn false;qa=qa-next;a=a-next;pa=pa-next;2、(10 分)typedef struct TreeNode char data;Struct TreeNode*lchild;Struct TreeNode*rchild;ListNode;BOOL PreOrderChar(TreeNode*T)if(T!=NULL)if(T-data=0)&(T-data=9)coutdata lchild);PreOrderChar(T-rchild);3、(15 分)typedef struct ListNode double cost;int num;Struct L

11、istNode*next;ListNode;BOOL AddTV(int m,double c,ListNode*L)ListNode*a,*p,*q;a=new ListNode;a-cost=c;a-num=m;if(L-next=NULL)a-next=L;L-next=a;else p=L;q=L-next;while(q-next!=L)&(c=q-cost)p=p-next;q=q-next;if(q-next=L)q-next=a;a-next=L;else p-next=a;a-next=q;课程名称：数据结构 -引言，算法分析，线性表 课程考试试卷课程考试试卷 题 号 一 二

12、 三 四 五 六 七 八 总分 阅卷 教师 得 分 一、单选题（每小题 2 分，共 10 分，本题所给四个答案中只有一个是正确的）1下面程序段的时间复杂度是 。sum=0;for(i=0;in*n;i+)sum+;（A）O(n/2)（B）O(n)（C）O(log2n)（D）O(n2)2下面程序段的时间复杂度是 。sum=0;for(i=0;ilink=p-link;p-link=s;（B）q-link=s;s-link=p;（C）p-link=s-link;s-link=p;（D）p-link=s;s-link=q;二、填空题（每空 1 分，共 5 分）1.从逻辑结构上讲，数据结构主要分为三大

13、类：线性结构 结构和网状结构。2.算法有效性的评价指标包括空间复杂度和 。3.堆栈的特点是_ ，队列的特点是_。4.在顺序表示的线性表中，插入一个新的记录的时间复杂度为_。三、判断题（若正确，在括号内打“”，否则打“”；每题 1 分，共 5 分）1线性表中的所有元素都有一个前驱和一个后继。（）2线性表是一种抽象数据类型。（）3算法的时间复杂度等于算法运行的时间。（）4由于顺序表中的记录是连续存储的，所以适合数据经常增加或删除的应用。（）5队列是一种操作受限的线性表。（）得 分 得 分 得 分 得 四、解析题（每题 10 分，共 50 分）1 简述下列概念：数据、数据元素、数据类型、数据结构、逻

14、辑结构、存储结构、线性结构、非线性结构。2 设 n 为正整数，利用大O记号，将下列程序段的执行时间表示为 n 的函数。i=1;k=0;while(in)k=k+10*i;i+;3设 n 个人围坐在一个圆桌周围，现在从第s 个人开始报数，数到第 m 个人，让他出局；然后从出局的下一个人重新开始报数，数到第 m 个人，再让他出局，如此反复直到所有的人全部出局为止。下面要解决的 Josephus 问题是：对于任意给定的 n,s 和 m，求出这n 个人的出局序列。请以 n=9,s=1,m=5 为例，人工模拟 Josephus 的求解过程以求得问题的解。4顺序表的插入和删除要求仍然保持各个元素原来的次序

15、。设在等概率情形下,对有 127个元素的顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移动多少个元素?5铁路进行列车调度时,常把站台设计成栈式结构的站台，如右图所示。试问：(1)设有编号为 1,2,3,4,5,6 的六辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?(2)若进站的六辆列车顺序如上所述,那么是否能够得到435612,325641,154623 和 135426 的出站序列,如果不能,说明为什么不能;如果能,说明如何得到(即写出进栈或出栈的序列)。五、算法设计题（每题 10 分，共 30 分）1已知数组存储了 n 个整数。下面给出了顺序查找算法，如果数组

16、中存在某个整数等于 K，返回 K 在数组的下标位置；否则返回1 表示数组中没有整数 K。请在算法的空缺处填入适当内容，使之能够正常工作。/值值 K如果在数组如果在数组 array 中返回存储的下标位置，否则返回中返回存储的下标位置，否则返回-1表示没有查找到。表示没有查找到。int binary(int R,int n,int K)int i;while()if(K=Ri);/在数组中在数组中 分 得 分 ;/不在数组中不在数组中 2假设线性表中存储了一些整数，试编写算法找到最大值。3设计一个算法，实现一个单链表的就地逆置（不另外增加多余的辅助空间）课程名称：数据结构-树、排序 课程考试试卷课

17、程考试试卷 题 号 一 二 三 四 五 六 七 八 总分 阅卷 教师 得 分 一、单选题（每小题 2 分，共 10 分，本题所给四个答案中只有一个是正确的）1将含有 100 个结点的完全二叉树从根结点开始顺序编号，根结点为第0 号，其他结点自上而下，同一层从左向右连续编号，则编号最小的叶子结点的编号为 。（A）47 （B）48 （C）49 （D）50 2对一颗二叉排序树进行 得到的结点序列是一个有序序列。（A）前序周游 （B）中序周游（C）后序周游 （D）层次周游 3设只含根结点的二叉树的高度为 1，则高度为 10 的二叉树,至少有_个结点。（A）10 （B）20 （C）30 （D）40 4如

18、果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。下列四种排序方法中 是稳定是稳定的排序方法。（A）shell 排序 （B）快速排序 （C）归并排序 （D）简单选择排序 5若表 R 在排序前已按键值递增顺序排列，则 算法的比较次数最少。（A）直接插入排序 （B）快速排序 （C）归并排序 （D）选择排序 二、填空题（每空 1 分，共 5 分）5.已知完全二叉树的第 5 层有 8 个结点(根结点在第 1 层),则其叶结点数是_。6.在有 n 个叶结点的 Huffman 树中,共有_个结点。7.采用_ _结构来存储和表示完全二叉树是最有效的。得 分

19、得 分 8.当记录个数比较少且基本有序时，_是最有效的排序方法。9.内部排序问题的时间复杂度的下限是 _ 。三、判断题（若正确，在括号内打“”，否则打“”；每题 1 分，共 5 分）1没有一个结点的二叉树称为空树。（）2一棵二叉树不能存储在一维数组中。（）3归并排序即适合内排序，也适合外排序。（）4快速排序在最差情况下的时间复杂度是 O（n2），此时它的性能并不比冒泡排序更好。（）5删除二叉排序树中的一个结点,再重新插入进去,一定能得到原来的二叉排序树。（）四、解析题（每题 10 分，共 50 分）2 根据下面的字母/频率表构造一棵 Huffman 树,并给出各字母的 Huffman 编码。A

20、 B C D E 1 4 9 16 25 3 已知一棵二叉树如下，请分别写出按前序、中序、后序和层次遍历时得到的结点序列。3请证明非空满二叉树的叶结点数等于其分支结点数加 1。4请画出把如下的完全二叉树构建成最大值堆的过程。5采用直接插入排序算法,对关键字序列(49,38,65,97,76,13,27)按从小到大的次序进行排序,写出每趟排序的结果。五、算法设计题（每题 10 分，共 30 分）1下面给出了冒泡排序的算法，请在算法的空缺处填入适当内容，使之能够正常工作，得到一个递增的序列。Void bubsort(Elem A,int n)/数组数组 R中有中有 n 个记录个记录 得 分 得 分 得 分 int i,j;Elem t；for(i=0;i+)for(int j=n-1;j-)if(Aj arraymid)low=mid+1;if(K=arraymid);if(K arraymid);/不在数组中不在数组中 2试设计一个图的深度优先搜索算法。3试设计一个图的广度优先搜索算法。得 分