数据结构习题库汇总(共16页).doc

精选优质文档-倾情为你奉上知识点：01绪论02顺序表03链表04栈05链队列06循环队列07串08数组的顺序表示09稀疏矩阵10广义表11二叉树的基本概念12二叉树遍历、二叉树性质13树、树与二叉树的转换14赫夫曼树15图的定义、图的存储16图的遍历17图的生成树18静态查找（顺序表的查找、有序表的查找）19动态查找（二叉排序树、平衡树、B树）20哈希查找21插入排序（直接插入、折半插入、2路插入、希尔排序）22选择排序（简单选择、树形选择、堆排序）23快速排序、归并排序101A1（1）数据的逻辑结构是（A）。 A数据的组织形式 B数据的存储形式 C数据的表示形式 D数据的实现形式101A1（2）组成数据的基本单位是（C）。 A数据项 B数据类型 C数据元素 D数据变量101B1（3）与顺序存储结构相比，链式存储结构的存储密度（B）。 A大 B小 C相同 D以上都不对101B2（4）对于存储同样一组数据元素而言，（D）。 A顺序存储结构比链接结构多占空间 B在顺序结构中查找元素的速度比在链接结构中查找要快 C与链接结构相比，顺序结构便于安排数据元素 D顺序结构占用整块空间而链接结构不要求整块空间101B2（5）下面程序的时间复杂度为（B）。 x=0； for（i=1；i<n；i+） for（j=i+1；j<=n；j+） x+； AO（） BO（n2） CO（1） DO（n）101B2（6）下面程序的时间复杂度为（C）。 for（i=0；i<m；i+） for（j=0；j<n；j+） Aij=i*j； AO（m2） BO（n2） CO（m×n） DO（m+n）101C2（7）下面程序段的执行次数为（B）。 for（i=0；i<n-1；i+） for（j=0；j>i；j+） state； An（n+1）/2 B（n-1）（n+2）/2 Cn（n+1）/2 D（n-1）（n+2）101D3（8）下面程序的时间复杂度为（A）。 for（i=0；i<m；i+） for（j=0；j<t；j+） cij=0； for（i=0；i<m；i+） for（j=0；j<t；j+） for（k=0；k<n；k+） cij=cij+aik*bkj； AO（m×n×t） BO（m+n+t） CO（m+n×t） DO（m×t+n）102A1（9）顺序表的特点是（B）。 A表中元素的个数为表长 B按顺序方式存储数据元素 C逻辑结构中相邻的结点在存储结构中仍相邻 D按表中元素的次序存储102C2（10）设顺序表共有n个元素，用数组elem存储，实现在第i个元素之前插入一个元素e的操作，其主要语句为（D）。 AFOR j=n DOWNTO i DO elemj=elemj+1； elemi=e； BFOR j=i TO n DO elemj=elemj+1； elemi=e； CFOR j=i TO n DO elemj+1=elemj； elemi=e； DFOR j=n DOWNTO i DO elemj+1=elemj； elemi=e；102D2（11）顺序表有5个元素，设在任何位置上插入元素是等概率的，则在该表中插入一个元素时所需移动元素的平均次数为（C）。 A3 B2 C25 D5102D2（12）设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（C）。 A9 B45 C7 D6102D3（13）设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为（B）。 A236 B239 C242 D245102D2（14）设顺序表的第5个元素的存储地址为200，且每个元素占一个存储单元，则第14个元素的存储地址为（B）。 A208 B209 C210 D214103D3（15）设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p->llink和p->rlink表示，则下列等式中（D）成立。 Ap=p->llink Bp=p->rlink Cp=p->llink->llink Dp=p->llink->rlink103A1（16）线性表采用链式存储时，其地址（D）。 A必须是连续的 B一定是不连续的 C部分地址必须是连续的 D连续与否均可以103B1（17）线性表是（A）。 A一个有限序列，可以为空 B一个有限序列，不可以为空 C一个无限序列，可以为空 D一个无限序列，不可以为空103B1（18）链式存储的线性表中的指针指向其（B）。 A前趋结点 B后继结点 C物理前趋 D物理后继103C2（19）设在链式存储的线性表中，设结点结构为 data link ，欲在p结点后插入一个结点q的关键步骤为（A）。 Aq->link=p->link； p->link=q； Bp->link=q->link； p->link=q； Cq->link=p->link； q->link=p； Dp->link=q->link； q->link=p；103C3（20）设有指针head指向的带表头结点的单链表，现将指针p指向的结点插入表中，使之成为第一个结点，其操作是（A）（其中，p->next、head->next分别表示p、head所指结点的链域）。 Ap->next=head->next； head->next=p； Bp->next=head->next； head=p； Cp->next=head； head=p； Dp->next=head； p= head；104A1（21）在栈中，下列说法正确的是（A）。 A每次插入总是在栈顶，每次删除也总是在栈顶。 B每次插入总是在栈顶，每次删除总是在栈底。 C每次插入总是在栈底，每次删除总是在栈顶。 D每次插入总是在栈底，每次删除也总是在栈底。104B2（22）设有一个栈，按A、B、C的顺序进栈，则下列（C）为不可能的出栈序列。 AABC BCBA CCAB DACB104B2（23）设有一个栈，按A、B、C、D的顺序进栈，则下列（D）为可能的出栈序列。 ADCAB BCDAB CDBAC DACDB104A2（24）顺序栈的上溢是指（B）。 A栈满时作退栈运算 B栈满时作进栈运算 C栈空时作退栈运算 D栈空时作进栈运算104D3（25）顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（D）。 Aselemtop=e； stop=stop+1； Bselemtop+1=e； stop=stop+1； Cstop=stop+1； selemtop+1=e； Dstop=stop+1； selemtop=e；104C2（26）设有5个元素A，B，C，D，E顺序进栈（进栈过程中可以出栈），出栈后依出栈次序进入队列，已知其出队次序为D，C，E，B，A，则该栈容量必定不小于（C）。 A2 B3 C4 D5104B2（27）设栈S的初始状态为空，现有五个元素组成的序列1，2，3，4，5，对该序列在栈S上依次进行PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作，出栈的元素序列是（C）。 A5，4，3，2，1 B2，1 C2，3 D3，4104B2（28）在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为（C）。 Atop不变 Btop=0 Ctop- - Dtop+104D3（29）向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行（B）。 Ahs->next=s； Bs->next=hs；hs=s； Cs->next=hs->next；hs->next=s； Ds->next=hs；hs=hs->next；105A1（30）在队列中，下列说法正确的是（A）。A每次插入总是在队尾，每次删除总是在队头。 B每次插入总是在队尾，每次删除也总是在队尾。C每次插入总是在队头，每次删除也总是在队头。 D每次插入总是在队头，每次删除总是在队尾。105D3（31）在带头结点的链队列q中，用qfront表示队头指针，qrear表示队尾指针，结点结构为data next ，删除链队列的队头结点的主要语句为（B）。 As=qfront； qfront->next= snext； Bs=qfront->next； qfront->next= snext； Cs=qfront->next； qfront= snext； Ds=q； qfront->next= snext；106C3（32）循环队列sq中，用数组elem存放数据元素，sqfront指示队头元素的前一个位置，sqrear指示队尾元素的当前位置，队列的最大容量为MAXSIZE，则队列满的条件为（D）。 Asqfront= sqrear Bsqfront= sqrear+1 C（sqfront +1）mod MAXSIZE= sqrear D（sqrear+1）mod MAXSIZE= sqfront106C2（33）循环队列sq中，用数组elem存放数据元素，sqfront指示队头元素的前一个位置，sqrear指示队尾元素的当前位置，队列的最大容量为MAXSIZE，则在队列未满时元素x入队列的主要操作为（A）。 Asqrear= （sqrear+1）mod MAXSIZE； sqelemsqrear=x； Bsqelemsqrear=x； sqrear= （sqrear+1）mod MAXSIZE； Csqfront= （sqfront+1）mod MAXSIZE； sqelemsqfront=x； Dsqelemsqfront=x； sqfront= sqfront+1；106B2（34）循环队列sq中，用数组elem025存放数据元素，sqfront指示队头元素的前一个位置，sqrear指示队尾元素的当前位置，设当前sqfront为20，sqrear为12，则当前队列中的元素个数为（D）。 A8 B16 C17 D18106B2（35）设循环队列的元素存放在一维数组Q030中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向（B）元素。 AQ4 BQ5 CQ14 DQ15105A1（36）队列操作的原则是（A）。 A先进先出 B后进先出 C只能进行插入 D只能进行删除105B2（37）一个队列的入列序列是1234，则队列的输出序列是（B）。 A4321 B1234 C1432 D3241108C2（38）设6行8列的二维数组A6×8=（aij）按行优先顺序存储，若第一个元素的存储位置为200，且每个元素占3个存储单元，则元素a54的存储位置为（B）。 A308 B305 C266 D269109C2（39）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（B）。 A13 B33 C18 D40108A1（40）设二个数组为A07、B-52，38，则这两个数组分别能存放的字符的最大个数是（C）。 A7和35 B1和5 C8和48 D1和6108C3（41）二维数组Mi，j的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下列j的范围从0到5。M按行存储时元素M3，5的起始地址与M按列存储时元素（B）的起始地址下同。 AM2，4 BM3，4 CM3，5 DM4，4108C2（42）设二维数组为M08，010，每个元素占2L个存储单元，以行序为主序存储，第一个元素的存储位置为P。存储位置为P+50L的元素为（A）。 AM2，3 BM2，2 CM3，3 DM3，4108C2（43）设二维数组A的维数界偶定义为18，010，起始地址为LOC，每个元素占2L个存储单元，以行序为主序存储方式下，某数据元素的地址为LOC+50L，则在列序为主序存储方式下，该元素的存储地址为（D）。 ALOC+28L BLOC+36L CLOC+50L DLOC+52L109B2（44）数组A140，130采用三元组表示，设数组元素与下标均为整型，则在非零元素个数小于（D）时，才能节省存储空间。 A1200 B401 C399 D400108A1（45）一维数组通常采用顺序存储结构，这是因为（C）。A一维数组是一种线性数据结构 B一维数组是一种动态数据结构C一旦建立了数组，则数组中的数据元素之间的关系不再变动 D一维数组只能采用顺序存储结构109A1（46）对稀疏矩阵进行压缩存储的目的是（B）。 A方便存储 B节省存储空间 C方便运算 D节省运算时间108D3（47）设二维数组a05，06按行存储，每个元素占d个存储单元，如果每个元素改为2d个存储单元，起始地址不变，则元素a2，6的存储地址将要增加（A）个存储单元。 A20d B21d C38d D39d108B2（48）一维数组与线性表的区别是（A）。 A前者长度固定，后者长度可变 B后者长度固定，前者长度可变 C两者长度均固定 D两者长度均可变107A1（49）下列关于串的叙述中，不正确的是（B）。 A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储107B2（50）以下论断正确的是（A）。 A“”是空串，“ ”是空白串 B“BEIJING”是“BEI JING”的子串 C“something”<“Somethig” D”BIT”=”BITE”107B2（51）字符串“VARTYPE unsignedint”若采用动态分配的顺序存储方法需要（C）个字节（假设每种数据均占用2个字节）。 A38 B动态产生，视情况而定 C40 D42111A1（52）由3个结点可以构造出（A）种不同形态的有向树。 A2 B3 C4 D5111A1（53）下列树的度为（B）。 A2 B3 C5 D8 112C2（54）含10个结点的二叉树中，度为0的结点有4个，则度为2的结点有（A）个。 A3 B4 C5 D6111B2（55）对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为（A）。 A98 B99 C97 D50112B2（56）一棵深度为8（根的层次号为1）的满二叉树有（B）个结点。 A256 B255 C128 D127112C3（57）设二叉树根结点的层数为1，若一棵高（深）度为h的二叉树只有度为0与度为2的结点，则其结点数至少为（B）。 Ah B2h-1 C2h D2h+1112C2（58）对下列二叉树进行先根次序遍历，所得次序为（A）。 AABCDEF BADCBFE CBCDAFE DDCBFEA112D3（59）一棵二叉树的前（先）序序列为ABCDEFG，则它的中序序列不可能为（C）。 ACBDAFEG BDCBAEFG CCDBAGEF DBDCAFGE112A1（60）若先序遍历二叉树的结果为结点序列A，B，C，则有（C）棵不同的二叉树可以得到这一结果。 A3 B4 C5 D6111B2（61）具有n个结点的二叉树，有（B）条边。 An Bn-1 Cn+1 D2n112C2（62）在具有n个结点的二叉树的二叉链表表示中，2n个孩子指针域中，只用到（B）个域。 An Bn-1 Cn+1 D2n114B2（63）对哈夫曼树，下列说法错误的是（B）。 A哈夫曼树是一类带树路径长度最短的树。 B给出一组数，构造的哈夫曼树唯一。 C给出一组数，构造的哈夫曼树的带树路径长度不变。 D哈夫曼树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和。111D3（64）假定在一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则叶子结点数为（B）。 A15 B16 C17 D47113C3（65）假定一棵三叉树的结点数为50，则它的最小高度为（C）。 A3 B4 C5 D6114B2（66）由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（D）。 A23 B37 C46 D44112C2（67）二叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则该二叉树根的右子树的根是（C）。 AE BF CG DH111A1（68）在完全二叉树中，若一个结点是叶结点，则它没有（C）。A左孩子结点 B右孩子结点 C左孩子和右孩子结点 D左孩子结点，右孩子结点和兄弟结点113B2（69）（B）二叉树，可以唯一地转化成一棵一般树。 A根结点无左孩子 B根结点无右孩子 C根据结点有两个孩子 D没有一棵111C2（70）具有65个结点的完全二叉树其深度为（B）。 A8 B7 C6 D5112C2（71）某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（B）的二叉树。 A空或只有一个结点 B高度等于其结点数 C任一结点无左孩子 D任一结点无右孩子113A1（72）下面叙述中，不正确的是（C）。 A线性表中除第一个元素和最后一个元素外，其他每个元素都有且仅有一个直接前驱和一个直接后继 B树中有且仅有一个结点没有前驱 C环形队列中任何一个元素都有且仅有一个直接前驱和一个直接后继 D在树中，一个结点可以有多个直接后继114B2（73）有m个叶子结点的哈夫曼树，其结点总数是（C）。 A2m B2m+1 C2m-1 D2（m+1）115A1（74）设图的邻接矩阵为，则该图有（A）个顶点。 A3 B4 C6 D9115B2（75）设图的邻接矩阵为，则该图为（A）。 A有向图 B无向图 C强连通图 D完全图115B2（76）设图的邻接链表如下图所示，则该图有（B）条边。 1 V1 2 3 4 2 V2 1 3 4 3 V3 1 2 4 V4 1 2 A4 B5 C10 D20115C2（77）设有6个结点的无向图，该图至少应有（B）条边才能确保是一个连通图。 A5 B6 C7 D8116D3（78）已知一有向图的邻接表存储结构如下，则根据有向图的深度优先遍历算法，从顶点V1出发，不能得到的顶点序列是（C）。 1 3 2 4 2 3 4 5 4 5 2 4 AV1V2V3V5V4 BV1 V3 V4V5V2 CV1V2V4V5V3 DV1 V4V3V5V2 119C3（79）下列图的深度优先遍历序列为（B）。 A B CD E F G H AABCDEFGH BABDHECFG CABEDHCFG DABCFGEDH115B1（80）对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（D）。 An B（n-1）2 C（n+1）2 Dn2 118B2（81）对含n个记录的顺序表进行顺序查找，在最坏情况下需要比较（B）次。 An-1 Bn C（n+1）/2 Dn（n-1）/2118B2（82）对含n个记录的有序表进行折半查找，设每个记录的查找概率相等，则平均查找长度的数量级为（C）。 AO（n） BO（n2） CO（） DO（1）119B2（83）有一棵二叉树如下图，该树是（B）。 50 20 95 10 30 55 70 85 A二叉平衡树 B二叉排序树 C堆的形状 D以上都不是119C3（84）已知10个数据元素（50，30，15，35，70，65，95，60，25，40），按照依次插入结点的方法生成一棵二叉排序树后，在查找成功的情况下，查找每个元素的平均比较次数（又称平均查找长度）为（C）。 A2.5 B3.2 C2.9 D2.7118C3（85）在顺序存储的线性表R029上进行分块查找（设分为5块）的平均查找长度为（D）。 A6 B11 C5 D6.5120D3（86）已知一个线性表（38，25，74，63，52，48），假定采用h（k）=k%7计算散列地址进行散列存储，若引用线性探测的开放定地址法解决冲突，则在该散列表上进行查找的平均查找长度为（C）。 A1.5 B1.7 C2 D2.3119A1（87）在一个3阶的B-树上，每个结点包含的子树相同，最多为（C）。 A1 B2 C3 D4120B2（88）设散列地址空间为0m-1，k为关键字，用P去除k，将余数作为k的散列地址，即：h（k）=k%P，为了减少发生冲突的可能性，一般取P为（B）。A小于m的最大奇数 B小于m的最大素数 C小于m的最大偶数 D小于m的最大合数120C3（89）设散列表表长m=14，散列函数为h（k）=k%11，表中已有4个记录，如果用二次探测再散列处理冲突，关键字为49的记录的存储地址是（D）。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 38 61 84 A8 B3 C5 D9119C3（90）已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为（C）。 A4 B5 C6 D7121B1（91）直接插入排序算法的时间复杂度为（B）。 AO（n） BO（n2） CO（） DO（1）121B2（92）设记录关键字序列为（84，67，21，50，33，79），采用对半插入排序方法自小到大进行排序时，记录的移动次数为（C）。 A9 B10 C19 D25123D3（93）下列四个序列中，（D）不是快速排序第一趟的可能结果。 A68，11，69，23，18，70，73 93 B11 68，69，23，18，70，73，93 C68，11，69，23，18 70 93，73 D18，11，23 93 68，70，69，73122C3（94）下列四个关键字序列中，（C）不是堆。 A05，23，16，68，94，72，71，73 B05，16，23，68，94，72，71，73 C05，23，16，73，94，72，71，68 D05，23，16，68，73，71，72，94123B2（95）从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为（D）。 A归并排序 B选择排序 C交换排序 D插入排序123B2（96）在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（D）。 AShell排序 B冒泡排序 C直接插入排序 D直接选择排序123B2（97）下列排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（B）。 A选择 B插入 C冒泡 D快速123C2（98）采用下列排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法有（A）。 A选择和插入 B冒泡和快速 C插入和快速 D选择和冒泡123D3（99）若用冒泡排序方法对序列10，14，26，29，41，52从大到小进行排序，需要进行（C）次比较。 A5 B10 C15 D25121C3（100）用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（C）。 A94，32，40，90，80，46，21，69 B32，40，21，46，69，94，90，80 C21，32，46，40，80，69，90，94 D90，69，80，46，21，32，94，40二、填空题101A1（1）数据结构按逻辑结构可分为两大类，它们分别是（线性结构和非线性结构）。101A1（2）算法的计算量的大小称为（计算的复杂度）。102B2（3）顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作的时间代价基本上都是等效的。则插入一个元素大约要移动表中的（n/2）个元素。103A2（4）顺序表相对于链表的优点有（节省存储）和（随机存取）。103B2（5）线性表的长度是（表中数据元素的个数）。103D3（6）在带有头结点的双链表L中，指针p所指结点是第一个元素结点的条件是（p=L->next；或L->next=p；）。103C3（7）某链表如下所示 info link p A B C D E 若要删除值为C的结点，应做操作（p->link=p->link->link）。104A1（8）对于栈只能在（栈顶）插入和删除元素。104C2（9）设有一空栈，现有输入序列1，2，3，4，5，6，经过push，push，pop，push，pop，push，push后，输出序列是（2、3）。106B2（10）有一个循环队列如下图，其队满条件是（front=(rear+1)%n），队列空的条件是（rear=front）。 front 队头指针 rear 队尾指针109B2（11）一个稀疏矩阵为，则对应的三元组线性表为（0，2，2），（1，0，3），（2，2，-1），（2，3，5）。108C2（12）设有二维数组A09，019，其每个元素占两个字节，数组按列优先顺序存储，第一个元素的存储地址为100，那么元素A6，6的存储地址为（232）。112B1（13）在一棵二叉排序树上按（中序）遍历得到的结点序列是一个有序序列。111C3（14）对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中（n-1）个用于链接孩子结点。112B2（15）对于下面的二叉树，按后序遍历得到的结点序列为（4，2，5，6，3，1）。 1 2 3 4 5 6115B1（16）设无向图G的顶点数为n，图G最少有（0）边。117C3（17）对下列图 1 6 2 5 3 4它的生成树有（6）棵。118C3（18）假定在有序表R019上进行二分查找，则比较三次查找成功的结点数为（4）。120D3（19）设有两个散列函数H1（K）=K mod 13和H2（K）=K mod 11+1，散列表为T012，用双重散列法（又称二次散列法）解决冲突。函数H1用来计算散列地址，当发生冲突时，H2作为计算下一个探测地址的地址增量。假定某一时刻散列表T的状态为： 0 1 2 3 4 5 6 7 8 9 10 11 12 T： 80 55 34下一个被插入的关键码为42，其插入位置是（0）。122C3（20）已知一棵二叉排序树如下图所示，则在查找成功的情况下查找每个元素的平均查找长度为（2.75）。 80 50 90 40 70 100 6