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

一、单项选择题（本大题共71小题，每小题2分，共142分）1、一个对象序列的排序码为46，79，56，38，40，84，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ c ）。（ ） a38，46，79，56，40，84 b38，79，56，46，40，84 c40，38，46，56，79，84 d38，46，56，79，40，84标准答案：c2、广义表（a）,a）的表头是（ c ）。（ ） aa bb c(a) d(a)标准答案：c3、数组a中，每个元素a的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址sa开始连续存放在存储器内，存放该数组至少需要的单元数是（ c ）。（ ） a80 b100 c240 d270标准答案：c4、在一个单链表hl中，若要向表头插入一个由指针p指向的结点，则执行（ ）。（ ） ahl=p；p-next=hl； bp-next=hl；hl=p； cp-next=hl；p=hl； dp-next=hl-next；hl-next=p；标准答案：b5、一个具有n个顶点的无向完全图的边数为（ ）。（ ） a(n+1)/2 bn(n-1)/2 cn(n-1) dn(n+1)标准答案：b6、如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。下列选项中，（ ）就是不稳定的排序方法。（ ） a起泡排序 b归并排序 c直接插入法排序 d简单选择排序标准答案：d7、按照二叉树的定义，具有3个结点的二叉树有（ ）种。（ ） a3 b4 c5 d6标准答案：c8、设有1000个元素，用二分法查找时，最大比较次数是（ ）。（ ） a1 b7 c10 d25标准答案：c9、树适合用来表示（ ）。（ ） a有序数据元素 b无序数据元素 c元素之间具有分支层次关系的数据 d元素之间无联系的数据标准答案：c10、设有两个串p和q，求p在q中首次出现的位置的运算称作（ ）。（ ） a连接 b模式匹配 c求子串 d求串长标准答案：b11、将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点x的双亲编号为（ ）。（ ） a23 b24 c25 d无法确定标准答案：a12、串的长度是（ ）。（ ） a串中不同字符的个数 b串中不同字母的个数 c串中所含字符的个数且字符个数大于0 d串中所含字符的个数标准答案：d13、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）。（ ） aacbed bdecab cdeabc dcedba标准答案：d14、顺序表中逻辑上相邻的节点其物理位置也（ ）。（ ） a一定相邻 b不必相邻 c按某种规律排列 d无要求标准答案：a15、数据结构是研究数据的（ ）以及它们之间的相互关系。（ ） a理想结构，物理结构 b理想结构，抽象结构 c物理结构，逻辑结构 d抽象结构，逻辑结构标准答案：c16、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。（ ） a24 b48 c53 d72标准答案：c17、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。（ ） a空或只有一个结点 b高度等于其结点数 c任一结点无左孩子 d任一结点无右孩子标准答案：b18、下列排序算法中，（ ）排序在每趟结束后不一定能选出一个元素放到其排好序的最终位置上。（ ） a选择 b冒泡 c归并 d堆标准答案：c19、广义表(a,b,c,d)的表尾是（ ）。（ ） aa bb c(a,b) d(b,c,d)标准答案：d20、具有65个结点的完全二叉树其深度为（ ）。（ ） a8 b7 c6 d5标准答案：b21、在内部排序中，排序时不稳定的有（ ）。（ ） a插入排序 b冒泡排序 c快速排序 d归并排序标准答案：c22、向堆中插入一个元素的时间复杂度为（ ）。（ ） ao(log2n) bo(n) co(1) do(nlog2n)标准答案：a23、在一个单链表hl中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行（ ）。（ ） aq-next=p-next；p-next=q； bp-next=q-next；q=p； cq-next=p-next；p-next=q； dp-next=q-next；q-next=p；标准答案：d24、线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。（ ） a必须是连续的 b部分地址必须是连续的 c一定不是连续的 d连续不连续都可以标准答案：d25、设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。（ ） ao（nlog2e） bo（n+e） co(ne) do(n2)标准答案：b26、队列操作的原则是（ ）。（ ） a先进先出 b后进先出 c只能进行插入 d只能进行删除标准答案：a27、在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（ ）。（ ） a行号 b列号 c元素值 d地址标准答案：a28、线性链表不具有的特点是（ ）。（ ） a随机访问 b不必事先估计所需存储空间大小 c插入与删除时不必移动元素 d所需空间与线性表长度成正比标准答案：a29、组成数据结构的基本单位是（ ）。（ ） a数据项 b数据类型 c数据元素 d数据变量标准答案：c30、设循环队列q1.n-1的头尾指针为f，r，当插入元素时尾指针r加1，头指针f总是指在队列中第一个元素的前一个位置，则队列中元素计数为（ ）。（ ） ar-f bn-（r-f） c（r-f+n）%n d（f-r+n）%n标准答案：c31、在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。（ ） a3 b2 c1 d1/2标准答案：b32、若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（ ）存储方式节省时间。（ ） a单链表 b双链表 c单循环链表 d顺序表标准答案：d33、若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ）方法比较次数最少。（ ） a直接插入排序 b快速排序 c归并排序 d直接选择排序标准答案：a34、下面程序段的时间复杂度为（ ）。 for(int i=0; im; i+) for(int j=0; jnext=p-next-next bp=p-next cp=p-next-next dp-next=p标准答案：a65、栈的插入与删除操作在（ ）进行。（ ） a栈顶 b栈底 c任意位置 d指定位置标准答案：a66、广义表（a），其表头是（ ）。（ ） aa b（a） c（） d（a）标准答案：b67、线索化二叉树中某结点d，没有左孩子的主要条件是（ ）。（ ） ad-lchild=null bd-ltag=1 cd-rchild=null dd-ltag=0标准答案：b68、在有n个叶子结点的哈夫曼树中，其结点总数为（ ）。（ ） a不确定 b2n c2n+1 d2n-1标准答案：d69、从一个循环顺序队列删除元素时，首先需要（ ）。（ ） a前移一位队首指针 b后移一位队首指针 c取出队首指针所指位置上的元素 d取出队尾指针所指位置上的元素标准答案：b70、substr(data structure，5，9)=（ ）。（ ） astructure bastuctur cdata structrue标准答案：a71、二分查找要求被查找的表是（ ）。（ ） a键值有序的链接表 b链接表但键值不一定有序 c键值有序的顺序表 d顺序表但键值不一定有序标准答案：c二、填空题（本大题共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； （3）f-prior=p； （4）p-next=f；85、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。标准答案：o(n);o(1)86、中缀表达示3+x*（2.4/5-6）所对应的后缀表达示为_。标准答案：3 x 2.4 5 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 所对应的后缀算术表达式为_。标准答案：3 4 25 6 15 + - / 8 * +90、快速排序在平均情况下的时间复杂度为_，在最坏情况下的时间复杂度为_。标准答案：o(nlog2n);o(n2)91、前序序列和中序序列相同的二叉树为_。标准答案：单右枝二叉树或孤立结点92、每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做_排序。标准答案：插入93、一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为_。标准答案：n(n+1)/294、后缀表达式“2 10 + 5 * 6 9 / ”的值为_。标准答案：695、对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为_，右孩子结点的编号为_。标准答案：2i;2i+196、假定一棵二叉树的结点数为18，则它的最小深度为_，最大深度为_。标准答案：5;1897、从一个栈删除元素时，首先取出_。标准答案：栈顶元素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、后缀算术表达式24 8 + 3 * 4 10 7 - * / 所对应的中缀算术表达式为_，其值为_。标准答案：(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;2110、若对一棵二叉树的结点编号从0开始顺序编码，按顺序存储，把编号为0的结点存储到a0中，其余类推，则ai元素的左孩子元素为_，右孩子元素为_。标准答案：2i+1;2i+2111、在一个具有n个顶点的无向完全图中，包含有_条边，在一个具有n个顶点的有向完全图中，包含有_条边。标准答案：n(n-1)/2;n(n-1)112、在一棵高度为h的3叉树中，最多含有_结点。标准答案：(3h-1)/2113、对于一个顺序实现的共享栈s1n，栈顶指针分别为top1和top2，top1由小到大，top2由大到小，其判断下溢的条件是_；判断上溢的条件是_。标准答案：top1=0或top2=n+1;top1+1=top2114、在循环双向链表中表头结点的左指针域指向_结点，最后一个结点的右指针域指向_结点。标准答案：表尾;表头115、每次从无序表中挑选出一个最大或最小元素，把它交换到有序表中的一端，此种排序方法叫做_排序。标准答案：选择116、对于一个以顺序实现的循环队列q0.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，请画出该二叉树。标准答案：121、（2.80）标准答案：122、对于结点类型为lnode的单链表，以下算法的功能为：_。void bb( lnode *& hl)lnode *p=hl; hl=null;while (p!=null)lnode *q=p;p=p-next;q-next=hl;hl=q;标准答案：将一个单链表按逆序链接。123、下面递归算法的功能是_。 void unknown(listnode *f，type &x) /指针f 是带表头结点的单链表的表头指针，数值x是给定值。listnode * temp; if (f-link!=null) while(f-linkdata=x) temp= f-link; f-link= temp-link ;delete temp; unknown(f-link , x); 标准答案：在单链表中删除所有值为x的结点。124、以下为向以bst为树根指针的二叉搜索树上插入值为item的结点的递归算法。请在横线处将程序补充完整。 void insert(btreenode*&bst,const elemtype&item) if(bst=null) btreenode* p=new btreenode; p-date=item; _; bst=p;else if(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）。标准答案：126、下列算法执行后得到的线性表la为：_。void bb(list &la)initlist(la);int a=78,26,56,27,34,42;for(i=0; i3; i+)insertfront(la,ai);for(i=3; i6; i+)insertrear(la,ai);traverselist(la);标准答案：（56，26，78，27，34，42）127、以上算法的功能为：_。void bb(list &l)int i=0;while (il.size)int j=i+1;while (jl.size)if(l.listj = =l.list)for (int k=j+1;kl.size;k+)l.listk-1=l.listk;l.size-;else j+;i+;标准答案：删除线性表中所有重复的元素。128、执行下面函数调用后得到的输出结果是_。void af(queue & q) initqueue(q); int a4 = 5,8,12,15 ; for ( int i=0; i4; i+ ) qinsert(q,ai); qinsert(q,qdelete(q); qinsert(q,30); qinsert(q,qdelete(q)+10); while ( ! queueempty(q) ) coutqdelete(q)data=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、以下算法用于实现“计算二叉数的的深度”。请在空白处填写语句，将程序补充完整。int btreedepth (btreenode *bt)if (bt= =null)return 0;elseint dep1,dep2;dep1=_;dep2=_;if (dep1dep2)_;return_;标准答案：btreedepth(bt-left)btreedepth(bt-right)return rep1+1rep2+1134、假定一个待散列存储的线性表为 (37,65,25,73,42,91,45,36,18,75)， 散列地址空间为ht12，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。标准答案：135、假定调用以下算法时栈 s 中已有2个元素（23，16），其中23是栈底。则调用后得到的栈内容为（从栈底开始排列）：_void cc( stack &s)pop(s);push(s,50);push(s,45);peek(s);标准