发布时间 : 星期日 文章吉林省计算机专升本历年真题资料更新完毕开始阅读175fb28e6529647d2728525d
A.(n+1)/2 B.n/2 C.n D.n+1
13.二维数组M的行下标i的范围从0到4，列下标j的范围从0到5，每个元素占4个存储单元，M按行序存储元素M[3][5]的起始地址与M按列序存储时元素（ ）的起始地址相同。 A. M[2][4] B. M[3][4] C. M[3][5] D. M[4][4]
14.一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。 A.3 B.4 C.5 D.6
15.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（ ） A．0 B.1 C.n D.n+1
16.已知一个图如下所示，若从从顶点a出发按深度优先搜索遍历，可能得到的一种遍历序列为（ ） A. a,b,e,c,d,f
B. a,c,f,e,b,d
C. a,e,d,f,c,b D.a,e,b,c,f,d
17.已知一个有向图如下所示，由该图得到的一种拓扑序列为（ ） A. V1,V4,V6,V2,V5,V3 B. V1,V2,V3,V4,V5,V6 C. V1,V4,V2,V3,V6,V5 D. V1,V2,V4,V6,V3,V5
18.对于一个长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的查找长度为（）
A. 3 B.4 C. 5 D.6
19.对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列是（）
A.1,3,5,7,9 B.5,7,9,1,3 C.5,3,1,7,9 D.9,7,5,3,1
20.一组记录的关键字为 （45,80,55,40,42,85）,则利用堆排序的方法建立的初始堆为（ ） A.(80,45,55,40,42,85) B.(85,80,55,45,42,40) C.(85,80,55,40,42,45) D.(85,55,80,42,45,40)
三、解答题（共５０分）
1．设有一种数据结构Ｂ的元素集合Ｋ和它的二元关系Ｒ为： B=(K,R)
K={K1,K2??K7}
R={
2. 将下面所示的森林转换成一棵二叉树（按字母序号顺序），并分别写出二叉树的先序、中序、后序的遍历序列。（6分）
3. 假设用于通信的电文有8个字母A,B,C,D,E,F,G,H组成，各字母在电文中出现的频率为5%，25%，4%，7%，9%，12%，30%，8%，试为这8个字母设计哈夫曼编码，并求其带权路长度WPL。(要求权值集取{5,25,4,7,9,12,30,8}，按照左子树权值小于右子树的权值的顺序构造哈夫曼树，并注明每个节点的权值。) (10分)
4对下面的带权图按照普里姆法从顶点V1出发构造一棵最小生成树，并求该生成树的权值。（要求：每加入一个结点，画一个图）（8分）
5，设有一组关键字（4，9，26，10，12，33，22，19），利用哈希函数为：H（key）=key，采用线性探测散列处理冲突，试在0～10的散列地址空间中对该组关键字构造哈希表，并求在关键字的查找概率相等的前提下查找成功的平均查找长度。（要求：直接写出哈希表格，查找长度表示为分数形式）（10分）
6，对长度为n的记录序列进行快速排序时，所需要的比较次数依赖于这几个元素的初始序列。点n=8时，在最好的情况下共需要进行多少次比较？（要求：写出每一趟的划分情况和比较次数。）（10分）
四，算法设计题（共10分）
试编写一个在带有头结点的双向循环链表中为x的结点之前，插入值为y的结点的算法。（要求：用C语言描述，结点类型定义为dlnode） Status InsertPrior-L(DlinkList &L)
五、程序填空题
1.华氏温度与摄氏度的转换公式为：C=5/9×（F-32），其中表示C摄氏温度，F表示华氏温度。要求输出从华氏0°到华氏300°，每隔20°一个值。 main()
{int upper,step;
float fahr=0.0,celsius; upper=300;step=20;
while( 2.求两数中的较大值。 #include {int a ,b,max; printf(“please input:\\n”); scanf(“%d%d”, ); max=a; max=b; printf(the max is :%d\\n“,max); } 3. 输入一行字符，分别统计出其中英文字母、空格、数字和其他字符的个数。 #include int letters=0,space=0,digit=0,other=0; printf(“please input characters\\ n”); while((c=getchar())! =?\\n?) {if(c>=?a?&&c<=?z?|| ) ; else if(c==? ?) ; else if (c>=?0?&&C<=?9?) ; else ; } printf(“%d%d%d%d\\n”,letter,space,digit,other); }