说明：本份试题满分100分，完成时间为90分钟。

请将答案写在答题纸上，不要写在试卷上，答题完毕将试卷、答题纸和草稿纸一起上交。

一、单选题（共20题计40分）1、输入序列为ABC，可以变为CBA时，经过的栈操作为（）A. push,pop,push,pop,push,popB. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,pop,push,push,pop,pop2．线程和进程最主要的区别在于A. 进程是UNIX下的概念，线程是Windows下的概念B. 进程的效率比线程低C. 在进程中可以创造线程，但线程中不能生成进程D. 进程由自己独立的运行空间，线程的运行空间是共享的3. IP路由发生在TCP/IP体系结构中的哪一层A. 物理层B. 数据链路层C. 网络层D. 传输层4. 假设一个IP主机地址为而子网掩码为那么该主机的网络号为_________5.120 C 、遍历是树形结构的一种重要运算。

若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是______。

供选择的答案A) E F G H B C D B) F E G H D C BC) B C D E F G H D) E F G C H D B6、五层完全二叉树有___个节点。

A. 16B. 32C. 31D. 337、用链接方式存储的非循环单向队列,在进行删除运算时,_____。

A) 头、尾指针可能都要修改B) 仅修改头指针C) 仅修改尾指针D) 头、尾指针都要修改8、如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（）A．插入排序B．归并排序C．冒泡排序D．堆排序9、对下列关键字序列用快速排序法进行排序时，速度最快的情形是：( )(A){25、23、30、17、21、5、9} (B){21、9、17、30、25、23、5}(C){21、25、5、17、9、23、30} (D){5、9、17、21、23、25、30}10、( ) 是用一组任意的存储单元存储线性表元素的一种数据结构。

A. 数组B. 链表C. 树D. 图11、循环单向链表指( )A. 最后一个节点的指针域总是指向链表头B. 可以自由膨胀的链表C. 链表含有指向上一级节点的指针域D. 都不是12、折半查找的时间复杂性为（）A. O（n*n）B. O（n）C. O（n*log2n）D. O（log2n）13、给出以下定义:char acX[ ]= "abcdefg";char acY[ ]= {'a','b','c','d','e','f','g'};则正确的叙述为( )A) 数组acX和数组acY等价B) 数组acX和数组acY的长度相同C) 数组acX的长度大于数组acY的长度D) 数组acX的长度小于数组Y的长度14、void example(char acHello[]){printf("%d", sizeof(acHello));return;}void main(){char acHello[] = "hello";example(acHello);return;}的输出是( )A 4B 5C 6 D不确定15、以下叙述中不正确的是( )A) 在不同的函数中可以使用相同名字的变量B) 函数中的形式参数是在栈中保存C) 在一个函数内定义的变量只在本函数范围内有效D) 在一个函数内的复合语句中定义的变量在本函数范围内有效(复合语句指函数中的成对括号构成的代码)16、以下程序运行后,输出结果是( )void main( ){char *szStr = "abcde";szStr += 2;printf("%lu \n",szStr);return;}A cdeB 字符c的ASCLL码值C "abcde"这个常串中字符c所在的地址D 出错17、语句switch(c)中的c不能是哪种数据类型A) char B) long C) unsigned D) double18、设有以下宏定义:#define N 4#define Y(n) ( (N+1)*n)则执行语句: Y(5+1)为____A) 30 B) 28 C)26 D)2419、下述算法的功能是_____。

/* L 是无头结点单链表*/LinkList Demo(LinkList L){ListNode *Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while (P->next) P=P->next;P->next=Q;Q->next=NULL;}return L;}A. 将单链表转变为循环链表B. 遍历操作，链表顺序不变C. 将链首节点移植至链尾D. 删除链首节点20、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。

A. BA+141B. BA+180C. BA+222D. BA+225二、多选题（共10题计30分）1、程序的局部变量存在于_______中，全局变量存在于________中，动态申请数据存在于________中。

A. 代码段B. 数据段C.堆栈D. 堆空间E. 程序2.下面关于临界资源的说法正确的有：A. 当关于某一组共享变量的所有临界区域均为空闲时，一个要求进入该组共享变量某一临界区的进程应当能够立即进入；B. 进程只能在临界区停留有限时间；C. 临界资源可以同时为两个以上的进程使用；D. 进程应该能够在有限的时间内进入临界区。

3、求出下列各小题中的时间复杂度：1)a= b;2)sum=0;for ( i = 0; i<n; i++)sum ++;3)sum=0;for ( j = 0; j<n; j++)for ( i = 0; i<j; i++)sum ++;4)sum=0;for ( j = 0; j<n; j*=2)for ( i = 0; i<n; i++)sum ++;A、O(1)B、O(n)C、O(n×n)D、O（n log2n）E、O（log2n）4、从下列有关树的叙述中,选出正确的叙述（）A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。

B．当K≥1时高度为K的二叉树至多有2k-1个结点。

C．用二叉树的前序遍历和中序遍历可以导出树的后序遍历。

D．将一棵树转换成二叉树后,根结点没有左子树。

5、设有六列火车，编号为1,2,3,4,5,6顺序开进一个栈式结构的站台，问下列输出序列中，哪些是可能出现的( )。

A．1,2,3,4,5,6B．6,5,4,3,2,1C．3,1,2,6,5,4D．3,2,1,6,5,46、双向链表存储结构如下，现有一该结构链表，某节点为p，该节点非首尾节点，删除该节点的正确操作是：typedef struct DulNode{struct DulNode *prior;ElemType data;struct DulNode *next;}DulNode,*DuLinkList;①p->prior->next = p->next;②p->prior->next = p->next->piror;③p->next->prior = p->prior;④p->next->prior = p->prior->next;⑤p->next->prior->next = p->next;⑥free(p);A. ③⑤⑥B. ①②⑥C. ②④⑥D. ①③⑥7、以下对结构体类型变量的定义中，正确的写法是:A) typedef struct aa B) #define AA struct aa{ int n; { int n;float m; float m;}AA; }td1;AA td1;C)struct{ D) struct{int n; int n;float m; float m;}aa; }td1;struct aa td1;8、下列定义正确的有：___A: char *pcPtr = "abcd";B: char pc[4]= "abcd";C: char pc[] = "abcd";D: char pc[] = 'abcd';E: char pc[] = {'a','b','c','d','\0'};F: char pc[] = 'a' 'b' 'c' 'd';9、有如下定义struct person{char name[9]; int age;};struct person class[10]={“Johu”, 17,“Paul”, 19“Mary”, 18,“Adam 16,};根据上述定义，若想输出字母M，下面错误的语句是A) prinft(“%c\n”,class[3].mane);B) pfintf(“%c\n”,class[3].name[0]);C) pfintf(“%c\n”,class[3].name[1]);D) p rinft(“%c\n”,class[2].name[1]);E) printf(“%c\n”,class[2].name[0]);10、IPv6是下一代IP协议。

IPv6的基本报头包含__ 个字节，此外还可以包含多今扩展报头。

基本报头中的_ 字段指明了一个特定的源站向一个特定目标站发送的分组序列，各个路由器要对该分组序列进行特殊的资源分配，以满足应用程序的特殊传输需求。

A．16 B．32 C．40 D．60E．负载长度F．数据流标记G．下一报头H．8h数限制三、改错题（共3题计15分）1、下列程序是否有错，请指出#define MAX_LEN 2_UC *ConvertCode(_UC *p_byte, _UC num){_UL i = 0;_UC strTemp[MAX_LEN];if (NULL == p_byte){return NULL;}memcpy(strTemp, p_byte, MAX_LEN);return (_UC *)strTemp;}void main(void){_UC str[MAX_LEN];str[0] = 0x12;str[1] = 0x34;ConvertCode(str, MAX_LEN);}2、请指出下面程序的错误：void GetMemory(char **ppcChar, int iLength){if(NULL == ppcChar){return;}*ppcChar = (char *)malloc(iLength);return;}void Test(void){char *szStr = NULL;GetMemory(&szStr, 100);if(NULL != szStr){strcpy(szStr, "hello");printf(szStr);}return;}3、请指出下面这段代码中的错误：unsigned long FUNC_B ( unsigned long ulCount ){unsigned long ulSum = 0 ;while( 0 <= ulCount ){ulSum += ulCount ;ulCount--;}return ulSum ;}四、应用题（15分）从键盘输入10个学生的学号和成绩，按成绩从大到小建立一个有序链表，并输出。