计算机技术基础题库 答案.doc

计算机技术基础题库答案一、选择题1 B 2 C 3 B 4 B 5 D 6 C 7 C 8 B 9 D 10D 11B 12B 13D 14C 15B 16C 17B 18C 19C 20A21D 22B 23C 24B 25A 26C 27C 28D 29B 30A 31C 32C 33D 34C 35C 36D 37A 38B 39B 40D41D 42D 43D 44C 45C 46A 47B 48D 49A 50B 51C 52C 53B 54B 55C 56C 57C 58B 59C 60D61C 62C 63C 64B 65C 66B 67C 68C 69A 70C 71C 72C 73A 74B 75C 76B 77B 78C 79 80C81C 82B D C 83D 84C 85A 86B 87A 88C 89B 90A 91C 92D 93B 94B 95C 96B 97D 98C 99B 100C101.D 102A 103C 104D 105C 106D 107A 108B 109B 110D 111B 112A 113D 114B 115B 116D 117C 118C 119B 120A 121C 122C 123D 124C 125A 126A 127C 128D 129B 130C 131A 132B 133D 134B 135A 136A 137D 138C 139B 140A 141D 142B 143A 144A 145B 146D 147、A 148、B 149、B 150、B151、D 152、D 153、A 154、C 155、B156、A 157、D 158、C 159、C 160、C161、D 162、D 163、C二、填空题1N/2 28个 33次 4n-15线性 任何 栈顶 队尾 队首 6顺序 链接7p.next s 82n-1 2n-1 2n-19中序 101 4 5 3.711按关键字排序 顺序存储 12顺序13栈 14双向队列15DBCA 16被排序的数据量大17记录按关键字排序而且是顺序存储18DCBA 19数据元素202 4 (23,38,15,) 21.定义指向某种类型对象的指针 取它所修饰的标识符地址 使用结构指针来访问结构中的成员（域）22、int *ptr = (int *)malloc(n*sizeof(int);23逻辑结构24线性结构 非线性结构 顺序 链接 索引 散列25由穷性 确定性 可行性 输入 输出26先进先出 27、中断本循环体循环 跳出本循环体本次循环，开始下一次循环28相邻位置 链接指针 29前驱 后继30p-next-next 31p-next s-data t32k-1 33n-1342i-1 352h-1 2h-1 2h-2+1362i 2i+1 i/2 (i-1)/2 37a4a3a2a138插入排序法 选择排序法 归并排序法 交换排序法39直接插入排序 直接选择排序 40（54,72,60,96,83）416 7 422 10 1143log2n+1 n 44245P-next=nil 46ls=nil ls=ls-next47r-next=s 48逻辑结构中相邻的结点在存储结构中仍相邻49便于插入和删除操作 50插入 删除51先进后出 先进先出 端点 52顺序存储结构和链式存储结构 s.top=-1 s.top=m-153Q.front=Q.rear Q.front=(Q.rear+1) mod M54(n+r-f) mod n55树中结点数目至少为1，二叉树的结点数目至少为0树中结点的最大度没有限制，二叉树结点的最大度数为2二叉树结点有左右子树之分，而树没有56只有一个根结点的树 空二叉树579 581次 7次59线性 非线性60顺序 链式 索引 散列存储61线性 62顺序 链式63顺序表 链式表 64链式 顺序65P-next66HL-next= =NULL；HL-next= =HL；67循环 68P-next-next69P-next q70P-next=head head=p 71相同72前驱 后继 73q74P-prior 75先进后出 先进先出 760 N-177栈顶指针 插入78栈顶元素 栈顶指针791 M-1 80P-next=top top=p81Top-next82Push(s,3) Pop(s) Push(s,5)83Pop(s) Pop(s) Push(s,d)84队尾 队首85Front=rear (r+1)%M= =front86(front+1)%M (r+1)%M870 N-1 88队尾指针 插入89P-next=NULL r=f=p90P-next=r-next r=r-next=p91(front=rear) & (front!=NULL) 或者 (front=rear) & (rear!=NULL)92空栈 空 只含有一个结点 931432943080 95N-196根 前驱 后继 977 1 4 1982 6 993 410010 4 3 1012 1 1 6102B I和J 1036 1042i 2i+1 i/210516 1065 8107A F 空 1082 2 3109a10 a11 a2110a2i+1 a2i+2 a(i-1)/21112n n-1 n+1112ABCDEF CBAEDF CBEFDA113(n+1)/2 1141 31156 19 11611117小于 小于118查找成功 左子树 右子树119左子树 右子树120插入 选择 1214122直接插入 123n-1 112438 46 79 56 40 84 1254 126冒泡1273 128412940 38 46 5 79 80 130快速1312132有穷的 确定的 能行的 有0到多个输入和1到多个输出 运算序列体现了解题规则133表 图 树 文件134顺序表135、前趋结点 1 后续 后续结点136、2k+1-1 2k+1-1三、简答题1插入一个结点要平均移动n/2结点；删除一个结点要平均移动(n1)/2 结点；具体的移动次数取决于n的大小和插入或删除的位置这两个因素。2在单链表中不能删除，而在双链表和单循环链表中可以删除p结点。3在循环单链表中可以由尾指针表示。4因为在顺序表中插入或删除时，需要移动大量的数据，所以在需要提高查找效率、而较少插入或删除的情况下，可以采用顺序存储；链式存储结构便于插入和删除，但是不便于查找结点，所以对于需要经常修改线性结点位置的情况下，采用链式存储为宜。5栈、队列都是一种线性结构，只是它们的运算规则不同。栈是遵循先进后出的运算规则，堆栈的操作只能在栈的一端（栈顶）进行；队列则遵循先进先出的运算规则队的操作只能在队列的队首删除，队尾插入。6（1）1324（2）能得到1432，不能得到1423。因为同时压入2，3，在弹出时根据栈的运算规则只能弹出3，2。（3）在1，2，3，4的各种排序中，根据堆栈的运算规则（先进后出），可能出现的次序是：1234，1324，1432，2143，2134，3214，4321。7循环队列的存储，可以解决假溢出问题。空的条件是队首追上队尾，即rear=front；满的条件是队尾追上队首，即rear+1=front。8两次对应的存储状态分别为：01234568034234567rear front 012345634153648 front rear9 先序遍历序列：ABDEFC中序遍历序列：DEFBAC后序遍历序列：FEDBCA10（1）由中序遍历序列和先序遍历序列，或中序遍历序列和后序遍历序列，可以惟一确定一棵二叉树。由先序序列知，根结点最先被访问，就可确定根结点为A，/而又由中序序列得知一棵树的根结点是其左、右子树的分割点，从而可确定以A为根的左子树结点为B，C，D，右子树结点为E，F，G。重复进行就可得到二叉树。（2）由先序遍历序列和后序遍历序列不能惟一确定一棵二叉树。因为两种遍历方法只能确定根结点，而分不清左右子树。11初始关键字序列为：（19，01，26，92，87，11，43，87，21）第一遍排序比较8次，交换6次后成为：（01，19，26，87，11，43，87，21，92）第二遍排序比较7次，交换3次后成为：（01，19，26，11，43，87，21，87，92）第三遍排序比较6次，交换2次后成为：（01，19，11，26，43，21，87，87，92）第四遍排序比较5次，交换2次后成为：（01，11，19，26，21，43，87，87，92）第五遍排序比较4次，交换1次后成为：（01，11，19，21，26，43，87，87，92）第一遍排序比较3次，交换0次。排序完毕。12、student1.num; ptr-num; (*ptr).num;13、栈：先进后出； 队列：先进先出。14枚举法的基本思想：先根据题目的部分条件确定答案的大致范围在此范围内对所有可能的情况逐一验证，直到全部验证完对某个情况使验证符合题目的条件，则为本题的一个答案，若全部情况验证完均不符合题目的条件，则问题无解。15数据结构是指相互有关联的数据元素的集合，其研究的内容有数据的逻辑结构、数据的存储结构（物理结构）以及数据的运算。16、DCBGFEA四、应用题1算法如下：/*从顺序表上统计出值为x的元素个数的算法*/int Count(sqlist &L，datatype x) int i=0，j； for(j=0；jnext；/*将指向第一个结点的指针赋给p*/ int i=0；/*将I 作为统计变量*/while(p!=NULL) if(p-data= = x)i+ +；p=p-next； return i；2算法如下：/*从顺序表中删除具有给定值x的所有元素*/void Delete(sqlist &L，datatype x) int I=0；while(IL.last) if(L.datai= =x)for(j=I+1;jnext!=NULL)q=p-next； if(q-data= = x)/*删除p的后继结点，即q结点*/ p-next=q-next； delete q； else p=p-next；3第（1）个序列可以得到，操作过程为：Push(S，A)，Push(S，B)，Push(S，C)，Pop(S)，Push(S，D)，Pop (S)，Pop (S)，Pop (S，A)，Push (S，E)，Pop (S)，Push (S，F)，Pop (S)，Pop (S) 。第（2）个序列可以得到，操作过程为：Push(S，A)，Pop(S)，Push(S，B)，Pop(S)，Push(S，C)，Push(S，D)，Push(S，E)，Pop(S)，Pop(S)，Push(S，F)，Pop(S)，Pop(S)。4二叉排序树如图所示。平均查找长度：382552163074689054725、 （1）初始状态 46 74 53 14 26 38 86 65 27 34第一趟 46 53 74 14 26 38 86 65 27 34第二趟 46 74 53 14 26 38 86 65 27 34第三趟 14 46 53 74 26 38 86 65 27 34第四趟 14 26 46 53 74 38 86 65 27 34第五趟 14 26 38 46 53 74 86 65 27 34第六趟 14 26 38 46 53 74 86 65 27 34第七趟 14 26 38 46 53 65 74 86 27 34第八趟 14 26 27 38 46 53 65 74 86 34第九趟 14 26 27 34 38 46 53 65 74 86（2）初始状态 46 74 53 14 26 38 86 65 27 34第一趟 46 53 14 26 38 74 65 27 34 86第二趟 46 14 26 38 53 65 27 34 74 86第三趟 14 26 38 46 53 27 34 65 74 86第四趟 14 26 38 46 27 34 53 65 74 86第五趟 14 26 38 27 34 46 53 65 74 86第六趟 14 26 27 34 38 46 53 65 74 86第七趟 14 26 27 34 38 46 53 65 74 86（3）初始状态 46 74 53 14 26 38 86 65 27 34第一趟 34 27 38 14 26 46 86 65 53 74第二趟 26 27 14 34 38 46 74 65 53 86第三趟 14 26 27 34 38 46 53 65 74 86第四趟 14 26 27 34 38 46 53 65 74 86（4）初始状态 46 74 53 14 26 38 86 65 27 34第一趟 14 74 53 46 26 38 86 65 27 34第二趟 14 26 53 46 74 38 86 65 27 34第三趟 14 26 27 46 74 38 86 65 53 34第四趟 14 26 27 34 74 38 86 65 53 46第五趟 14 26 27 34 38 74 86 65 53 46第六趟 14 26 27 34 38 46 86 65 53 74第七趟 14 26 27 34 38 46 53 65 86 74第八趟 14 26 27 34 38 46 53 65 86 74第九趟 14 26 27 34 38 46 53 65 74 866、循环栈中元素（从栈顶到栈底）输出1CA2E CB3E CD4(E )C5CE6(C)7C8F7、出队函数编程如下： Type QPop(Queue *q)if(q-size = 0)QError(“QDelete:Queue is Empty”);int Temp;Temp = (q-rear + MaxQueuesize q-size)%MaxQueuesize;q-size-;return(q-dataTemp);8、入队函数编程如下： Type QPush(Queue *q,Type item)if(q-size = MaxQueuesize)QError(“QDelete:Queue is Full”);int Temp;Temp = (q-front +q-size- MaxQueuesize)%MaxQueuesize;q-dataTemp = item;q-size+;9进制转换函数编程如下： #include #include “stack.h”void MultiBase(long n,int B)int m;Stack S;SetStack(S);while(n!=0) Push(&S,n%B); n=n/B;while(!StEmpty(&S) m=Pop(&S); if(m10) printf(“%d”,m); else printf(“%c”,m+87);printf(“n”);10直接选择排序程序如下：void SelectSort(int *pa, int n)int i,temp;i=0;for(i=0;in-1;i+)int min=i;int j;for(j=i+1;jn;j+) if(pajpamin) min=j;if(min!=i) temp=pai; pai=pamin; pamin=temp;11、冒泡排序程序如下：void Bubble(int *pa, int n)int i,j,temp,last;i=0;while(