数据结构（本）-002-国开机考复习资料

本文档的说明：文档是由网络收集整理而来！仅供考前复习使用！第1题:单选题向顺序栈中压入新元素时，应当（）。先移动栈顶指针，再存入元素先存入元素，再移动栈顶指针先后次序无关紧要同时进行参考答案是：先移动栈顶指针，再存入元素第2题:单选题两个字符串相等的条件是（）。串的长度相等含有相同的字符集都是非空串两个串的长度相等且对应位置的字符相同参考答案是：两个串的长度相等且对应位置的字符相同第3题:单选题广义表(f,h,(a,b,d,c),d,e,((i,j),k))的长度是()。61084参考答案是：6第4题:单选题在长度为n（n>1）的（）上，删除第一个元素，其算法的时间复杂度为O(n)。只有首结点指针h的不带头结点的单向循环链表只有尾结点指针r的不带头结点的单向循环链表只有尾结点指针r的带头结点h的单向循环链表只有头结点指针h的单向循环链表参考答案是：只有首结点指针h的不带头结点的单向循环链表第5题:单选题在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。1/2124参考答案是：2第6题:单选题下列的叙述中，不属于算法特性的是（）。可行性输入性可读性有穷性参考答案是：可读性第7题:单选题利用2、4、5、10这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（）。18163830参考答案是：38第8题:单选题两个字符串相等的条件是（）。两串的长度相等两串包含的字符相同两串的长度相等，并且两串包含的字符相同两串的长度相等，并且对应位置上的字符相同参考答案是：两串的长度相等，并且对应位置上的字符相同第9题:单选题在一个长度为n的顺序表中为了删除第5个元素，由第6个元素开始从后到前依次移动了15个元素。则原顺序表的长度为（）。19202125参考答案是：20第10题:单选题已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列从小到大排序，经过一趟冒泡排序后的序列为（）。16，28，34，54，73，62，60，26，43，9528，16，34，54，62，73，60，26，43，9516，28，34，54，62，60，73，26，43，9528，16，34，54，62，60，73，26，43，95参考答案是：28，16，34，54，62，73，60，26，43，95第11题:单选题一棵二叉树采用链式存储，n个结点的二叉树共有（）个指针域为空。n-1nn+1不确定参考答案是：n+1第12题:单选题（）的一个重要应用是解决主机和打印机之间速度不匹配的问题。双向链表循环链表栈队列参考答案是：队列第13题:单选题在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86时，经（）次比较后查找成功。3468参考答案是：4第14题:单选题下面的应用中，不符合栈的后进先出特点的是（）。从键盘上输出一批整数，然后按相反次序输出验证一个算数表达式的括号是否配对十进制数转换为二进制数算数运算、逻辑运算和关系运算参考答案是：算数运算、逻辑运算和关系运算第15题:单选题在双向循环双链表中，删除*p结点需要（）。p->next->prior=p->prior;p->prior->next=p->next;p->prior->next=p->next;p->next->prior=p->prior;p->prior->next=p;p->prior=p->prior->prior;p->prior=p->next->next;p->next=p->prior->prior;参考答案是：p->prior->next=p->next;p->next->prior=p->prior;第16题:判断题采用顺序查找法对长度为n（n为偶数）的线性表进行查找，采用从前向后的方向查找。在等概率条件下成功查找到前n/2个元素的平均查找长度为(n+2)/4。√×参考答案是：√第17题:判断题哈夫曼树叶结点数比非叶结点数多1。√×参考答案是：√第18题:判断题线性表是一个有限序列，不可以为空。√×参考答案是：×第19题:判断题若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。√×参考答案是：×第20题:判断题设有一个单向链表，结点的指针域为next，头指针为head，p指向尾结点，为了使该单向链表改为单向循环链表，可用语句p->next=head。√×参考答案是：√第21题:判断题对于一棵深度为4的满三叉树，其结点数为40。√×参考答案是：√第22题:判断题用字符数组存储长度为n的字符串，数组长度至少为n+1。√×参考答案是：√第23题:判断题链接存储表示中数据元素之间的逻辑关系是由指针表示的。√×参考答案是：√第24题:判断题使用邻接矩阵存储图的时候，占用空间大小与图的结点个数没有关系。√×参考答案是：×第25题:判断题序列3,1,7,18,6,9,13,12经一趟归并排序的结果为1,3,7,18,6,9,13,12。√×参考答案是：×第26题:判断题队列的特性是先进后出。√×参考答案是：×第27题:判断题对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行号、列号和元素值三项信息。√×参考答案是：√第28题:判断题在有序表A[1…18]中，采用二分查找算法查找元素值等于A[17]的元素，所比较过的元素的下标依次是9、14、16、17。√×参考答案是：√第29题:判断题森林是m（m≥0）棵互不相交的树的集合。√×参考答案是：√第30题:判断题图的连通分量是无向图的极大连通子图。√×参考答案是：√第31题:单选题以下是冒泡排序算法对存放在a[1],a[2],...,a[n]中序列按关键字key由小到大排序，完成程序中空格部分。voidbsort(NODEa[],intn){inti,j,flag;NODEtemp;for(j=1;j<=n-1;j++){flag=0;for(i=1;i<=n-j;i++)if(______________){flag=1;temp=a[i];a[i]=a[i+1];a[i+1]=temp;}if(flag==0)break;}}a[i].key>a[i+1].keya[i].key<a[i+1].keya[j].key>a[j+1].keya[j].key<a[j+1].key参考答案是：a[i].key>a[i+1].key第32题:单选题设某二叉树先序遍历为abdec，中序遍历为dbeac。该二叉树的图形是（）。参考答案是：第33题:单选题以下程序段的结果是：c的值为（）chara[]=”abcdefgjh”；int*p=a,c=0;While(*p++)c++;891011参考答案是：9第34题:单选题二叉排序树结点类型定义如下：typedefstructBnode{intkey;structBnode*left;structBnode*right;}Bnode;以下为二叉排序树的查找算法，完成程序中空格部分。Bnode*BSearch(Bnode*bt,intk){

Bnode*p;if(bt==NULL)return(bt);p=bt;while(________){if(k<p->key)p=p->left;elsep=p->right;if(p==NULL)break;}return(p);}p->key==kp->key!=kbt==NULLbt!=NULL参考答案是：p->key!=k第35题:单选题在下面空格处填写一条语句，以使下面的进栈算法完整。voidPush(struct