《数据结构》复习题题库.doc 24页

'一、单项选择题（本大题共71小题，每小题2分，共142分）1、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（C）。（）A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}标准答案：C2、广义表（（a）,a）的表头是（C）。（）A．aB．bC．(a)D．((a))标准答案：C3、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（C）。（）A．80B．100C．240D．270标准答案：C4、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。（）A．HL=p；p->next=HL；B．p->next=HL；HL=p；C．p->next=HL；p=HL；D．p->next=HL->next；HL->next=p；标准答案：B5、一个具有n个顶点的无向完全图的边数为（）。（）A．(n+1)/2B．n(n-1)/2C．n(n-1)D．n(n+1)标准答案：B6、如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。下列选项中，（）就是不稳定的排序方法。（）A．起泡排序B．归并排序C．直接插入法排序第24页共24页 D．简单选择排序标准答案：D7、按照二叉树的定义，具有3个结点的二叉树有（）种。（）A．3B．4C．5D．6标准答案：C8、设有1000个元素，用二分法查找时，最大比较次数是（）。（）A．1B．7C．10D．25标准答案：C9、树适合用来表示（）。（）A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据标准答案：C10、设有两个串p和q，求p在q中首次出现的位置的运算称作（）。（）A．连接B．模式匹配C．求子串D．求串长标准答案：B11、将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（）。（）A．23B．24C．25D．无法确定标准答案：A12、串的长度是（）。（）A．串中不同字符的个数B．串中不同字母的个数C．串中所含字符的个数且字符个数大于0D．串中所含字符的个数第24页共24页 标准答案：D13、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。（）A．acbedB．decabC．deabcD．cedba标准答案：D14、顺序表中逻辑上相邻的节点其物理位置也（）。（）A．一定相邻B．不必相邻C．按某种规律排列D．无要求标准答案：A15、数据结构是研究数据的（）以及它们之间的相互关系。（）A．理想结构，物理结构B．理想结构，抽象结构C．物理结构，逻辑结构D．抽象结构，逻辑结构标准答案：C16、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。（）A．24B．48C．53D．72标准答案：C17、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。（）A．空或只有一个结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子标准答案：B18、下列排序算法中，（）排序在每趟结束后不一定能选出一个元素放到其排好序的最终位置上。（）A．选择B．冒泡C．归并第24页共24页 D．堆标准答案：C19、广义表(a,b,c,d)的表尾是（）。（）A．aB．bC．(a,b)D．(b,c,d)标准答案：D20、具有65个结点的完全二叉树其深度为（）。（）A．8B．7C．6D．5标准答案：B21、在内部排序中，排序时不稳定的有（）。（）A．插入排序B．冒泡排序C．快速排序D．归并排序标准答案：C22、向堆中插入一个元素的时间复杂度为（）。（）A．O(log2n)B．O(n)C．O(1)D．O(nlog2n)标准答案：A23、在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行（）。（）A．q->next=p->next；p->next=q；B．p->next=q->next；q=p；C．q->next=p->next；p->next=q；D．p->next=q->next；q->next=p；标准答案：D24、线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。（）A．必须是连续的B．部分地址必须是连续的C．一定不是连续的D．连续不连续都可以第24页共24页 标准答案：D25、设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。（）A．O（nlog2e）B．O（n+e）C．O(ne)D．O(n2)标准答案：B26、队列操作的原则是（）。（）A．先进先出B．后进先出C．只能进行插入D．只能进行删除标准答案：A27、在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。（）A．行号B．列号C．元素值D．地址标准答案：A28、线性链表不具有的特点是（）。（）A．随机访问B．不必事先估计所需存储空间大小C．插入与删除时不必移动元素D．所需空间与线性表长度成正比标准答案：A29、组成数据结构的基本单位是（）。（）A．数据项B．数据类型C．数据元素D．数据变量标准答案：C30、设循环队列Q[1..N-1]的头尾指针为F，R，当插入元素时尾指针R加1，头指针F总是指在队列中第一个元素的前一个位置，则队列中元素计数为（）。（）A．R-FB．N-（R-F）C．（R-F+N）%N第24页共24页 D．（F-R+N）%N标准答案：C31、在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。（）A．3B．2C．1D．1/2标准答案：B32、若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（）存储方式节省时间。（）A．单链表B．双链表C．单循环链表D．顺序表标准答案：D33、若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（）方法比较次数最少。（）A．直接插入排序B．快速排序C．归并排序D．直接选择排序标准答案：A34、下面程序段的时间复杂度为（）。for(inti=0;inext=p->next->nextB．p=p->nextC．p=p->next->nextD．p->next=p标准答案：A65、栈的插入与删除操作在（）进行。（）A．栈顶B．栈底C．任意位置第24页共24页 D．指定位置标准答案：A66、广义表（（a）），其表头是（）。（）A．aB．（a）C．（）D．（（a））标准答案：B67、线索化二叉树中某结点D，没有左孩子的主要条件是（）。（）A．D->Lchild=NullB．D->ltag=1C．D->Rchild=NullD．D->ltag=0标准答案：B68、在有n个叶子结点的哈夫曼树中，其结点总数为（）。（）A．不确定B．2nC．2n+1D．2n-1标准答案：D69、从一个循环顺序队列删除元素时，首先需要（）。（）A．前移一位队首指针B．后移一位队首指针C．取出队首指针所指位置上的元素D．取出队尾指针所指位置上的元素标准答案：B70、Substr("DATASTRUCTURE"，5，9)=（）。（）A．STRUCTURE"B．"ASTUCTUR"C．"DATASTRUCTRUE"标准答案：A71、二分查找要求被查找的表是（）。（）A．键值有序的链接表B．链接表但键值不一定有序C．键值有序的顺序表D．顺序表但键值不一定有序标准答案：C第24页共24页 二、填空题（本大题共48小题，每小题2分，共96分）72、数据的存储结构被分为顺序结构、链接结构、___、散列结构四种。标准答案：索引结构73、数据的存储结构被分为顺序结构、链接结构、索引结构、___四种。标准答案：散列结构74、在双向链表中每个结点包含有两个指针域，一个指向其___结点，另一个指向其___结点。标准答案：前驱;后继75、在一个图中，所有顶点的度数之和等于所有边数的___倍。标准答案：276、对于一棵具有n个结点的树，该树中所有结点的度数之和为___。标准答案：n-177、假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为3的结点数为___个。标准答案：278、一个算法应具备的5个特性为___、确定性、可行性、输入、输出。标准答案：有穷性79、一个算法应具备的5个特性为有穷性、___、可行性、输入、输出。标准答案：确定性80、以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为___。标准答案：37/1281、对于线性表(18,25,63,50,42,32,90)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为0的元素有___个，散列地址为5的元素有___个。标准答案：3;282、数据的存储结构被分为顺序结构、___、索引结构、散列结构四种。标准答案：链接结构83、对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为___。标准答案：n*n84、在双向循环链表中，在指针p所指的结点之后插入指针f所指的结点，其操作为___。标准答案：（1）f->next=p->next；（2）p->next->prior=f；第24页共24页 （3）f->prior=p；（4）p->next=f；85、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为___，在表尾插入元素的时间复杂度为___。标准答案：O(n);O(1)86、中缀表达示3+X*（2.4/5-6）所对应的后缀表达示为___。标准答案：3x2.45／6－*＋87、假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为0的结点数为___个。标准答案：788、对于线性表（18，25，63，50，41，32，90，66）进行散列存储时，若选用H（K）=K%11作为散列函数，则散列地址为3的元素有___个，散列地址为8的元素有___个。标准答案：1;289、中缀算术表达式3+4/(25-(6+15))*8所对应的后缀算术表达式为___。标准答案：3425615+-/8*+90、快速排序在平均情况下的时间复杂度为___，在最坏情况下的时间复杂度为___。标准答案：O(nlog2n);O(n2)91、前序序列和中序序列相同的二叉树为___。标准答案：单右枝二叉树或孤立结点92、每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做___排序。标准答案：插入93、一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为___。标准答案：n(n+1)/294、后缀表达式“210+5*6–9/”的值为___。标准答案：695、对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为___，右孩子结点的编号为___。标准答案：2i;2i+196、假定一棵二叉树的结点数为18，则它的最小深度为___，最大深度为___。标准答案：5;1897、从一个栈删除元素时，首先取出___。第24页共24页 标准答案：栈顶元素98、在线性表的___存储中，对每一个元素只能采用顺序查找。标准答案：链接99、一棵深度为5的满二叉树中的结点数为___个。标准答案：31100、一个算法应具备的5个特性为有穷性、确定性、___、输入、输出。标准答案：可行性101、在线性表的单链接存储结构中，每个结点包含有两个域，一个叫___域，另一个叫___域。标准答案：元素值;指针102、当从一个小根堆中删除一个元素时，需要把堆尾元素填补到___位置，然后再按条件把它逐层___调整。标准答案：堆顶;向下103、假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为2的结点数为___个。标准答案：2104、从有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素时，其查找长度分别为___和___。标准答案：1;3105、在散列表（Hash）查找中，评判一个散列函数优劣的两个主要条件是：___和___。标准答案：值均匀分布于表空间以减少冲突;函数尽可能简单以方便计算106、后缀算术表达式248+3*4107-*/所对应的中缀算术表达式为___，其值为___。标准答案：(24+8)*3/(4*(10-7));8107、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则应执行语句：___。标准答案：p->next=HL；HL=p；108、假定一组记录的排序码为（46，79，56，38，40，80，25，34），在对其进行快速排序的过程中，进行第一次划分后得到的排序码序列为___。标准答案：（40，34，25，38，46，80，56，79）109、对于线性表（18，25，63，50，41，32，90，66）进行散列存储时，若选用H（K）=K%11作为散列函数，则散列地址为0的元素有___个散列地址为8的元素有___个。标准答案：1;2第24页共24页 110、若对一棵二叉树的结点编号从0开始顺序编码，按顺序存储，把编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左孩子元素为___，右孩子元素为___。标准答案：2i+1;2i+2111、在一个具有n个顶点的无向完全图中，包含有___条边，在一个具有n个顶点的有向完全图中，包含有___条边。标准答案：n(n-1)/2;n(n-1)112、在一棵高度为h的3叉树中，最多含有___结点。标准答案：(3h-1)/2113、对于一个顺序实现的共享栈S[1…n]，栈顶指针分别为top1和top2，top1由小到大，top2由大到小，其判断下溢的条件是___；判断上溢的条件是___。标准答案：top1=0或top2=n+1;top1+1=top2114、在循环双向链表中表头结点的左指针域指向___结点，最后一个结点的右指针域指向___结点。标准答案：表尾;表头115、每次从无序表中挑选出一个最大或最小元素，把它交换到有序表中的一端，此种排序方法叫做___排序。标准答案：选择116、对于一个以顺序实现的循环队列Q[0...m-1]，队头、队尾指针分别为f，r，其判空的条件是___，判满的条件是___。标准答案：r=f;(r+1)%m=f117、假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为1的结点数为___个。标准答案：0118、在一棵树中，___没有前驱结点。标准答案：树概结点119、以二分查找方法查找一个线性表时，此线性表必须是___存储的___表。标准答案：顺序;有序三、简答题（本大题共20小题，每小题10分，共200分）120、已知一棵二叉树的中序遍历结果为DBHEAFICG，前序遍历结果为ABDEHCFIG，请画出该二叉树。标准答案：第24页共24页 121、（2.80）标准答案：122、对于结点类型为Lnode的单链表，以下算法的功能为：____________________________。voidBB(LNode*&HL){　　LNode*p=HL;　　HL=NULL;　　while(p!=NULL)　　{　　　　LNode*q=p;　　　　p=p->next;第24页共24页 　　　　q->next=HL;　　　　HL=q;　　}}标准答案：将一个单链表按逆序链接。123、下面递归算法的功能是_____________________________。voidunknown(ListNode*f，Type&x){//指针f是带表头结点的单链表的表头指针，数值x是给定值。　　ListNode*temp;if(f->link!=NULL){while(f->linkàdata==x){temp=f->link;f->link=temp->link;deletetemp;}unknown(f->link,x);}}标准答案：在单链表中删除所有值为x的结点。124、以下为向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法。请在横线处将程序补充完整。VoidInsert(BtreeNode*&BST,constElemType&item)　{if(BST==NULL)　　{BTreeNode*p=newBTreeNode;　　p->date=item;　　______________________________;　　BST=p;　　　}　　　elseif(itemdate)___________________________;　　　else______________________________;　}（2.80）标准答案：p->left=p->right=NULLInsert(BST->left，item)Insert(BST->right，item)125、设有顺序表中的元素依次为017，094，154，170，275，503，512，553，612，677，765，897，908。试画出对其进行折半搜索时做性能分析用的扩充二叉搜索树（判定树），并计算搜索成功时的平均搜索长度（ASLsucc）和搜索不成功进的平均搜索长度（ASLunsucc）。标准答案：第24页共24页 126、下列算法执行后得到的线性表La为：___。voidBB(List&La){　　InitList(La);　　inta[]={78,26,56,27,34,42};　　for(i=0;i<3;i++)　　　　InsertFront(La,a[i]);　　for(i=3;i<6;i++)　　　　InsertRear(La,a[i]);　　TraverseList(La);}标准答案：（56，26，78，27，34，42）127、以上算法的功能为：_________。voidBB(List&L){　　inti=0;　　while(idata=item;LNode*p=HL;while(p->next!=HL)　　p=p->next;　newptr->next=HL;　p->next=newptr;}标准答案：向单链表的末尾添加一个元素。131、标准答案：（3，4）5，（0，1）8，（4，5）9，（4，7）10，（2，4）14，（1，3）15，（4，6）31132、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。标准答案：EDCBIHJGFA133、以下算法用于实现“计算二叉数的的深度”。请在空白处填写语句，将程序补充完整。intBtreeDepth(BTreeNode*BT){if(BT==NULL)return0;else{intdep1,dep2;dep1=__________________________;dep2=__________________________;if(dep1>dep2)__________________________;return___________________;}}标准答案：BtreeDepth(BT->left)BtreeDepth(BT->right)第24页共24页 returnrep1+1rep2+1134、假定一个待散列存储的线性表为(37,65,25,73,42,91,45,36,18,75)，散列地址空间为HT[12]，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。标准答案：135、假定调用以下算法时栈S中已有2个元素（23，16），其中23是栈底。则调用后得到的栈内容为（从栈底开始排列）：_________________________voidCC(Stack&S){　　Pop(S);　　Push(S,50);　　Push(S,45);　　Peek(S);}标准答案：23，50，45136、对于结点类型为LNode的单链表，以下算法的功能为：_____________________________intAA(LNode*HL,ElemTypex){intn=0;LNode*p=HL;while(p!=NULL){if(p->data==x)n++;p=p->next;}returnn;}标准答案：统计单链表中结点的值等于给定值x的结点数137第24页共24页 、以下算法的功能是_________________________，一般称之为_________________________算法。voidDD(ElemTypeA[],intn){　　ElemTypex;　　inti,j,flag;　　for(i=1;i=i;j--)if(A[j].stn=i-1;j--)L.list[j+1]=L.list[j];L.list[i-1]=x;L.size++;}139、编写对二叉树进行中序遍历的非递归算法。标准答案：voidInorder(BTreeNode*BT){　　BtreeNode*s[10];　　inttop=-1;　　BTreeNode*p=BT;　　while(top!=-1||p!=NULL)　　{　　　　while(p!=NULL)　　　　{　　　　　top++;　　　　　s[top]=p;　　　　　p=p->left;　　　　}　　if(top!=-1)　　　{　　　　p=s[top];　　　　top--;　　　　cout<data<<’‘;　　　　p=p->right;　　　}　　}}第24页共24页'