资源描述：
《计算机软件基础试题2.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2004年计算机软件基础试题一、一、选择题（30分） 1、线性表若采用链式存储结构时，要求内存中可用储存单元的地址___。A．必须是连续的B.部分地址必须是连续的C．一定是不连续的D.连续或不连续都可以（） 2、栈和队列的共同点是___。A．都是先进后出B．都是先进先出C．只允许在端点处插入和删除元素D．没有共同点（） 3、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行___。A．s—＞next=p;p—＞next=s;B．s—＞next=p—＞next;p—＞next=s;C．s—＞next=p—＞next;p=s;D．p—＞next=s;s—＞n
2、ext=p;（） 4、向一个栈顶指针为HS（HS所指结点为实际结点）的链栈中插入一个s所指结点时，则执行____。A．HS—＞next=s;B．s—＞next=HS—＞next;HS—＞next=s;C．s—＞next=HS;HS=s;D．s—＞next=HS;HS=HS—＞next;（） 5、具有6个顶点的无向图至少应有____条边才能确保是一个连通图。A．5B．6C．7D．8（） 6、如图所示的4棵二叉树中，不是完全二叉树的是____。 ABCD（） 7、对线性表进行二分查找时，要求线性表必须_______。A．顺序方式存储B．链接方式存储C．顺序方式存储，且结点按关键
3、字有序排序D．以链接方式存储，且结点按关键字有序排序（） 8、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度的___。A．nB．n/2C．（n+1）/2D．(n-1)/2（） 9、在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是___。A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;C．p->next=s;p->next->prior=s;s->prior=p;s->n
4、ext=p->next;D．s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;（） 10、一组纪录的关键字为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为___。A．38,40,56,79,46,84B．40,38,46,79,56,84C．40,38,46,56,79,84D．38,46,56,79,40,84（） 11、一组纪录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个纪录为基准得到的一次划分结果为____。A．38,40,46,79,56,84B．4
5、0,38,46,79,56,84C．40,38,46,56,79,84D．38,46,56,79,40,84（） 12、有一个散列表，表长度m为100，采用除留余数法构造散列函数，即H(K)=KmodP（P≤m），为使散列函数有较好的性能，P的选择应该是_____________。A．99B．97C．91D．93（） 13、一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列是_____________。A．12345B．54321C．23451D．41235（） 14、15、已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为___
6、;按广度搜索法进行遍历，则可能得到的一种顶点序列为____。 ①A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b（）②A．a,b,c,e,d,fB．a,b,d,e,f,dC．a,e,b,c,f,dD．a,c,e,b,f,d（）二、判断题（5分） 1、（）如果对于无向图G，图中任意两个顶点Vi，Vj都是连通的，称图G为连通图。 2、（）链表的物理存储结构具有同链表一样的顺序。 3、（）深度为k的二叉树至多有2k个结点（k>=1）。 4、（）在多个栈空间共享的问题上，使用链栈容易出现单个栈满而其余栈空的情况。 5、（）在栈满
7、情况下不能作进栈运算，否则产生“上溢”。 三、填空题（10分） 1、下面程序段的时间复杂度是_____。i=s=0;while(s＜＝n){i=i+1;s=s+i;} 2、在二叉链表中，判断某指针P所指结点为叶子结点的条件是____________________________________。 3、在采用顺序存储结构的线性表中，插入或删除一个元素，需要平均移动__________元素，具体移动的元素个数与__________有关。 4、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5
