下载文档原格式
习题解答一、单项选择题1.若定义了int n=2, *p=&n, *q=p;则下面【】的赋值是非法的。
A.p=qB. *p=*qC. n=*qD. p=n【答案】D2.若定义了double *p, a;则能通过scanf函数给输入项读入数据的程序段是【】。
A.p=&a; scanf(“%1e”,p);B. *p=&a; scanf(“%1f”,p);C. p=&a; scanf(“%f”,p);D. p=&a; scanf(“%1f”,a);【答案】C3.若定义了int a[10], i=3, *p; p=&a[5];下面不能表示为a数组元素的是【】。
A.p[-5]B. a[i+5]C. *p++D. a[i-5]【答案】D4.若有如下定义：int n[5]={1,2,3,4,5},*p=n;则值为５的表达式是【】。
A.*+5B. *（p+5）C. *p+=4D. p+4【答案】C5.设变量b的地址已赋给指针变量ps，下面为“真”的表达式是【】。
A.b==&psB. b==psC. b==*psD. &b==&ps【答案】C6.设有以下定义和语句：int a[3][2]={1,2,3,4,5,6},*p[3];p[0]=a[1];则*(p[0]+1)所代表的数组元素是【】。
A.a[0][1]B. a[1][0]C. a[1][1]D. a[1][2]【答案】C7.若定义了char *str=”Hello!”;下面程序段中正确的是【】。
A.char c[ ], *p=c; strcpy(p,str);B.char c[5], *p; strcpy(p=&c[1],&str[3]);C.char c[5]; strcpy(c,str);D.char c[5]; strcpy(p=c+2,str+3);【答案】B8.若有下面的程序段，则不正确的fxy函数的首部是【】。
第6章设备管理习题与解答6.1 例题解析例6.2.1 何谓虚拟设备？请说明SPOOLing系统是如何实现虚拟设备的。
解本题的考核要点是虚拟设备的实现方法。
虚拟设备是指利用软件方法，比如SPOOLing系统，把独享设备分割为若干台逻辑上的独占的设备，使用户感受到系统有出若干独占设备在运行。
当然，系统中至少一台拥有物理设备，这是虚拟设备技术的基础。
SPOOLing系统又称“假脱机I/O系统”，其中心思想是，让共享的、高速的、大容量外存储器（比如，磁盘）来模拟若干台独占设备，使系统中的一台或少数几台独占设备变成多台可并行使用的虚拟设备。
SPOOLing系统主要管理外存上的输入井和输出井，以及内存中的输入缓冲区和输出缓冲区。
其管理进程主要有输入和输出进程，负责将输入数据装入到输入井，或者将输出井的数据送出。
它的特点是：提高了 I/O操作的速度；将独占设备改造为共享设备；实现了虚拟设备功能。
例 6.2.2 有关设备管理要领的下列叙述中，( )是不正确的。
A．通道是处理输入、输出的软件B．所有外围设备都由系统统一来管理C．来自通道的I/O中断事件由设备管理负责处理D．编制好的通道程序是存放在主存贮器中的E．由用户给出的设备编号是设备的绝对号解本题的考核要点是设备管理的基本概念。
(1) 通道是计算机上配置的一种专门用于输入输出的设备，是硬件的组成部分。
因此A是错误的。
(2) 目前常见I/O系统其外部设备的驱动和输入输出都由系统统一管理。
因此B是对的。
(3) 设备管理模块中的底层软件中配有专门处理设备中断的处理程序。
通道中断属于设备中断的一种。
因此C是对的。
(4) 通道设备自身只配有一个简单的处理装置（CPU），并不配有存储器，它所运行的通道程序全部来自内存。
因此D是对的。
(5) 系统在初启时为每台物理设备赋予一个绝对号，设备绝对号是相互独立的。
由用户给出的设备号只能是逻辑编号，由系统将逻辑号映射为绝对号。
因此E是错误的。
一、基础知识题6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。
【解答】设度为m的树中度为0,1,2,…,m的结点数分别为n0, n1, n2,…, nm，结点总数为n，分枝数为B，则下面二式成立n= n0+n1+n2+…+nm (1)n=B+1= n1+2n2 +…+mnm+1 (2)由(1)和(2)得叶子结点数n0=1+即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=86.2一棵完全二叉树上有1001个结点，求叶子结点的个数。
【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则n= n0+ n1+ n2n=2n0+n1-11002=2n0+n1由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。
本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，……。
虽然解法也对，但步骤多且复杂，极易出错。
6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。
【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。
6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。
【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。
若完全二叉树有501个结点，则叶子数251，度为2的结点数是250，度为1的结点数为0。
6.5 某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是多少。
第六章的练习题一、选择题1．设无向图的顶点个数为n ，则该图最多有（ ）条边。
A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0E ．n2 2．一个n 个顶点的连通无向图，其边的个数至少为（ ）。
A ．n-1B ．nC ．n+1D ．nlogn ； 3．要连通具有n 个顶点的有向图，至少需要（ ）条边。
A ．n-lB ．nC ．n+lD ．2n 4．n 个结点的完全有向图含有边的数目（ ）。
A ．n*nB ．n （n ＋１）C ．n ／2D ．n*（n －l ） 5．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。
A ．0 B ．1 C ．n-1 D ．n6．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A ．1/2B ．2C ．1D ．47．一个图中包含K 个连通分量，若按深度优先搜索方法访问所有结点，则必须调用（ ）次深度优先搜索遍历算法。
A ．1B ．K-1C ．KD ．K+1 8．下列哪一种图的邻接矩阵是对称矩阵？（ ）A ．有向图B ．无向图C ．AOV 网D ．AOE 网9． 从邻接阵矩可以看出，该图共有（①）个顶点；如果是有向图该图共有（②） 条弧；如果是无向图，则共有（③）条边。
①．A ．9 B ．3 C ．6 D ．1 E ．以上答案均不正确 ②．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 ③．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 10．对某个无向图的邻接矩阵来讲，（ ）。
A ．第i 行上的非零元素个数和第i 列的非零元素的个数一定相等B ．矩阵中的非零元素个数等于图中的边数C ．第i 行上，第i 列上非零元素总数等于顶点vi 的度数D ．矩阵中非全零行的行数等于图中的顶点数11．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
第6章设备管理习题与解答6.1 例题解析例6.2.1 何谓虚拟设备？请说明SPOOLing系统是如何实现虚拟设备的。
解本题的考核要点是虚拟设备的实现方法。
虚拟设备是指利用软件方法，比如SPOOLing系统，把独享设备分割为若干台逻辑上的独占的设备，使用户感受到系统有出若干独占设备在运行。
当然，系统中至少一台拥有物理设备，这是虚拟设备技术的基础。
SPOOLing系统又称“假脱机I/O系统”，其中心思想是，让共享的、高速的、大容量外存储器（比如，磁盘）来模拟若干台独占设备，使系统中的一台或少数几台独占设备变成多台可并行使用的虚拟设备。
SPOOLing系统主要管理外存上的输入井和输出井，以及内存中的输入缓冲区和输出缓冲区。
其管理进程主要有输入和输出进程，负责将输入数据装入到输入井，或者将输出井的数据送出。
它的特点是：提高了 I/O操作的速度；将独占设备改造为共享设备；实现了虚拟设备功能。
例 6.2.2 有关设备管理要领的下列叙述中，( )是不正确的。
A．通道是处理输入、输出的软件B．所有外围设备都由系统统一来管理C．来自通道的I/O中断事件由设备管理负责处理D．编制好的通道程序是存放在主存贮器中的E．由用户给出的设备编号是设备的绝对号解本题的考核要点是设备管理的基本概念。
(1) 通道是计算机上配置的一种专门用于输入输出的设备，是硬件的组成部分。
因此A是错误的。
(2) 目前常见I/O系统其外部设备的驱动和输入输出都由系统统一管理。
因此B是对的。
(3) 设备管理模块中的底层软件中配有专门处理设备中断的处理程序。
通道中断属于设备中断的一种。
因此C是对的。
(4) 通道设备自身只配有一个简单的处理装置（CPU），并不配有存储器，它所运行的通道程序全部来自内存。
因此D是对的。
(5) 系统在初启时为每台物理设备赋予一个绝对号，设备绝对号是相互独立的。
由用户给出的设备号只能是逻辑编号，由系统将逻辑号映射为绝对号。
因此E是错误的。
第六章练习题1 采用二分法查找，要求线性表必须（C ） A. 用链表实现B. 用顺序方式、任意序存储C. 顺序存储，且按关键大小排列D. 顺序存储且按关键字由小到大排列 2．给定序列｛3，5，7，9，11，13，15，17｝：（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树。
画出插入完成后的二叉排序树，并求其在等概率情况下查找成功的平均查找长度。
（2）按表中元素顺序构造一棵二叉平衡树，并求其在等概率情况下查找成功的平均查找长度，与（1）比较，可得出什么结论？(1)按输入顺序进行插入后的二叉排序树如图（一）所示。
具有等概率下查找成功的平均查找长度为29)87654321(81=+++++++=succ ASL 。
（2）构造的一棵平均二叉树如图（二）所示。
其在等概率下查找成功的平均查找长度为411)543221(81=+⨯+⨯+=succ ASL 。
与（1）相比，可见在同样序列的查找中，二叉平衡树比二叉排序树的平均查找长度要小，查找效率较高。
3．折半查找排序的时间复杂度是（ D ）。
A ．O （n 2）B ．O （nlog 2n ）C ．O （n ）D ．O （log 2n ）4．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（B ）型调整以使其平衡。
A. LL B. LR C. RL D. RR5．某顺序存储的表格中有90000个元素，已按关键字值额定升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同。
用顺序查找法查找时，平均比较次数约为（ C ）。
A ．25000B ．30000C ．45000D ．900006. 最好的情况下，在顺序表中按值查找一个元素算法时间的复杂度是（D ）。
A. O(n)B. O(n )C. O(log 2n)D. O(1) 7．散列文件是一种（ D ）。
数据结构第六章题⽬讲解02⼀选择题：1、以下说法错误的是①树形结构的特点是⼀个结点可以有多个直接前趋②线性结构中的⼀个结点⾄多只有⼀个直接后继③树形结构可以表达(组织)更复杂的数据④树(及⼀切树形结构)是⼀种"分⽀层次"结构⑤任何只含⼀个结点的集合是⼀棵树2．深度为6的⼆叉树最多有( )个结点①64 ②63 ③32 ④313 下列说法中正确的是①任何⼀棵⼆叉树中⾄少有⼀个结点的度为2②任何⼀棵⼆叉树中每个结点的度都为2 ⼆叉树可空③任何⼀棵⼆叉树中的度肯定等于2 ④任何⼀棵⼆叉树中的度可以⼩于24 设森林T中有4棵树，第⼀、⼆、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成⼀棵⼆叉树后，且根结点的右⼦树上有（）个结点。
①n1-1 ②n1③n1+n2+n3④n2+n3+n4⼆．名词解释：1 结点的度 3。
叶⼦ 4。
分⽀点 5。
树的度三填空题⼆叉树第i(i>=1)层上⾄多有_____个结点。
1、深度为k(k>=1)的⼆叉树⾄多有_____个结点。
2、如果将⼀棵有n个结点的完全⼆叉树按层编号，则对任⼀编号为i(1<=i<=n)的结点X有：若i=1,则结点X是_ ____；若i〉1,则X的双亲PARENT(X)的编号为__ ____。
若2i>n，则结点X⽆_ _____且⽆_ _____；否则，X的左孩⼦LCHILD(X)的编号为____。
若2i+1>n，则结点X⽆__ ____；否则，X的右孩⼦RCHILD(X)的编号为_____。
4．以下程序段采⽤先根遍历⽅法求⼆叉树的叶⼦数，请在横线处填充适当的语句。
Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶⼦数count的初值为0*/ {if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))__ __;countleaf(t->lchild,&count);countleaf(t->rchild,&count);}}5 先根遍历树和先根遍历与该树对应的⼆叉树，其结果_____。
C语言程序设计– 第六章课后习题电子13-02班王双喜一、选择题1. C语言中一维数组的定义方式为：类型说明符数组名（C）A. [整型常量]B. [整型表达式]C. [整型常量]或[整型常量表达式]D. [常量表达式]2. C语言中引用数组元素时，下标表达式的类型为（C）A. 单精度型B. 双精度型C. 整型D. 指针型3. 若有定义：int a[3][4];，则对a数组元素的非法引用是（D）A. a[0][3*1]B. a[2][3]C. a[1+1][0]D. a[0][4]（解释：A、B、C均正确，D看起来引用不太妥当，但其亦有其意义（a[0][4]等价于a[1][0]））4. 若有定义：int a[][3] = {1, 2, 3, 4, 5, 6, 7, 8, 9};，则a数组的第一维大小是（C）A. 1B. 2C. 3D. 4（解释：共9个元素，除以3即可得第一维大小是3；若有余数，则应加1）5. 若有定义：int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};，则值为5的表达式是（C）A. a[5]B. a[a[4]]C. a[a[3]]D. a[a[5]]6. 要求定义包含8个int类型元素的一维数组，以下错误的定义语句是（A）A. int N = 8;int a[N]; B. #define N 3while (a[2*N+2];C. int a[] = {0, 1, 2, 3, 4, 5, 6, 7};D. int a[1+7] = {0};（解释：数组的大小必须是整型常量或整型常量表达式）7. 若二维数组a有m列，则在a[i][j]前的元素个数为（A）A. i * m + jB. j * m + iC. i * m + i - 1D. i * m + j - 18. 下面是对数组s的初始化，其中不正确的是（D）A. char s[5] = {"abc"};B. char s[5] = {'a', 'b', 'c'};C. char s[5] = "";D. char s[5] = "abcdef";（解释：D中元素个数太多，算上'\0'共六个，非法）9. 下面程序段的运行结果是（B）char c[] = "\t\v\\\0will\n";printf("%d", strlen(c));A. 14B. 3C. 9D. 字符串中有非法字符，输出值不确定（解释：字符串中第四个是'\0'即结束标志，因此字符串长度是3）10. 判断字符串s1是否等于s2，应当使用（D）A. if (s1 == s2)B. if (s1 = s2)C. if (strcpy(s1, s2))D. if (strcmp(s1, s2) == 0)（解释：对于字符串来讲，其名字的内容是该字符串的起始地址，不能通过比较名字来比较相等，而应该用专用的函数进行逐字符匹配）二、写出程序的执行结果1. 程序一：# include <stdio.h>main(){int a[3][3] = {1, 3, 5, 7, 9, 11, 13, 15, 17};int sum = 0, i, j;for (i = 0; i < 3; i++)for (j = 0; j < 3; j++){a[i][j] = i + j;if (i == j) sum = sum + a[i][j];}printf("sum = %d", sum);}执行结果：打印sum = 6.（解释：a中各个元素的值是其行和列数字之和，sum内保存a中对角线元素之和，即sum = 0 + 2 + 4）2. 程序二：# include <stdio.h>main(){int i, j, row, col, max;int a[3][4] = {{1, 2, 3, 4}, {9, 8, 7, 6}, {-1, -2, 0, 5}};max = a[0][0]; row = 0; col = 0;for (i = 0; i < 3; i++)for (j = 0; j < 4; j++)if (a[i][j] > max){max = a[i][j];row = i;col = j;}printf("max = %d, row = %d, col = %d\n", max, row, col);}执行结果：打印max = 9, row = 1, col = 0.（解释：此程序的功能是逐行逐列扫描元素，总是将最大的元素赋给max，并保存该元素的行数和列数；因此执行完毕后，max是最大的元素(9)，row是其行数(1)，col是其列数(0)）3. 程序三：# include <stdio.h>main(){int a[4][4], i, j, k;for (i = 0; i < 4; i++)for (j = 0; j < 4; j++)a[i][j] = i - j;for (i = 0; i < 4; i++){for (j = 0; j <= i; j++)printf("%4d", a[i][j]);printf("\n");}}执行结果：第一行打印0；第二行打印1 0；第三行打印2 1 0；第四行打印3 2 1 0。
第6章习题一、填空1．结点数为7的二叉树的高度最矮是，最高是。
2．给定二叉树的结点数，要使树高为最大，那么该树应该是形状。
3．给定二叉树的结点数，要使树高为最矮，那么该树应该是形状。
4．如果一棵满二叉树的深度为6，那么它共有个结点，有个叶结点。
5．有15个结点的二叉树，最少有个叶结点，最多有个叶结点。
6．由n个带权值的叶结点生成的哈夫曼树，最终共有个结点。
7．将一棵完全二叉树按层次进行编号。
那么，对编号为i的结点，如果有左孩子，则左孩子的编号应该是；如果有右孩子，则右孩子的编号应该是。
8．若二叉树共有n个结点，采用二叉链表存储结构。
那么在所有存储结点里，一共会有个指针域，其中有个指针域是空的。
9．深度为5的二叉树，至多有个结点。
10．在二叉树中，有一个结点具有左、右两个孩子。
那么在中序遍历序列里，它的右孩子一定排在它的边。
二、选择1．在所给的4棵二叉树中，不是完全二叉树。
2．把一棵深度为3的左单支二叉树改造成完全二叉树时，要增添个空结点。
A．10 B．8 C．6 D．43．设有一棵5个结点的二叉树，其先序遍历序列为：A-B-C-D-E，中序遍历序列为：B-A-D-C-E，那么它的后序遍历序列为。
A．A-B-D-E-C B．B-D-E-C-AC．D-E-C-A-B D．A-B-C-D-E4．将一棵有50个结点的完全二叉树按层编号，那么编号为25的结点是。
A．无左、右孩子B．有左孩子，无右孩子C．有右孩子，无左孩子D．有左、有孩子5．深度为6的二叉树，最多可以有个结点。
A．63 B．64 C．127 D．1286．在一棵非空二叉树的中序遍历序列里，根结点的右边结点。
A．只有左子树上的部分B．只有左子树上的所有C．只有右子树上的部分D．只有右子树上的所有7．在任何一棵二叉树的各种遍历序列中，叶结点的相对次序是。
A．不发生变化B．发生变化C．不能确定D．以上都不对8．权值为1、2、6、8的四个结点，所构造的哈夫曼树的带权路径长度是。
