电大数据结构(本)小抄

中央电大开放本科计算机科学与技术数据结构（本一、单项选择题1．数据元素是数据的基本单位，它（C）。A．只能有一个数据项组成B．至少有二个数据项组成C．可以是一个数据项也可以由若干个数据项组成D．至少有一个数据项为指针类型2．一种逻辑结构（A）存储结构。A．可以有不同的B．只能有唯一的C．的数据元素在计算机中的表示称为D．的数据元素之间的关系称为3．线性表的顺序结构中，（C）。A．逻辑上相邻的元素在物理位置上不一定相邻B．数据元素是不能随机访问的C．逻辑上相邻的元素在物理位置上也相邻D．进行数据元素的插入、删除效率较高4．以下说法中不正确的是（B）。A．双向循环链表中每个结点需要包含两个指针域B．已知单向链表中任一结点的指针就能访问到链表中每个结点C．顺序存储的线性链表是可以随机访问的D．单向循环链表中尾结点的指针域中存放的是头指针5．以下表中可以随机访问的是（D）。A．单向链表B．双向链表C．单向循环链表D．顺序表6．双向循环链表结点的数据类型为：structnode{intdata;structnode*next;/*指向直接后继*/structnode*prior;}；设p指向表中某一结点，要显示p所指结点的直接前驱结点的数据元素，可用操作（B）。A．printf(“%d”,p->next->data);B．printf(“%d”,p->prior->data);C．printf(“%d”,p->prior->next);D．printf(“%d”,p->data);7.设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（A）。A．(n+1)/2B．nC．2nD．n-i8．一个栈的进栈序列是efgh，则栈的不可能的出栈序列是（D）（进出栈操作可以交替进行）。A．hgfeB．gfehC．fgehD．ehfg9．设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x接收栈顶元素，则出栈操作为（A）。A．x=top->data;top=top->next;B．top=top->next;x=top->data;C．x=top->next;top=top->data;D．top->next=top;x=top->data;10．设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x接收栈顶元素，则取栈顶元素的操作为（C）。A．top->data=x;B．top=top->next;C．x=top->data;D．x=top->data;top=top->next;11．以下说法正确的是（C）。A．队列是后进先出B．栈的特点是后进后出C．栈的删除和插入操作都只能在栈顶进行D．队列的删除和插入操作都只能在队头进行13．串函数StrCmp(“abA”,”aba”)的值为（D）。A．1B．0C．“abAaba”D．-114．char*p;p=StrCat(“ABD”,”ABC”);Printf(“%s”,p);的显示结果为（B）。A．-1B．ABDABCC．ABD．115．设有一个12阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中（矩阵A的第一个元素为a1,1，数组b的下标从1开始），则矩阵A中第4行的元素在数组b中的下标i一定有（A）。A、7≤i≤10B、11≤i≤15C、9≤i≤14D、6≤i≤916．深度为5的满二叉树至多有（B）个结点（根结点为第一层）A．40B．31C．34D．3517．已知一个图的边数为m，则该图的所有顶点的度数之和为（A）。A．2mB．mC．2m+1D．m/218．已知一个图的所有顶点的度数之和为m，则该图的边数为（D）。A．2mB．mC．2m+1D．m/219．以下说法不正确的是（D）。A．连通图G一定存在生成树B．连通图G的生成树中一定包含G的所有顶点C．连通图G的生成树中不一定包含G的所有边D．连通图G的生成树可以是不连通的20．以下说法不正确的是（A）。A．连通图G的生成树一定是唯一的B．连通图G一定存在生成树C．连通图G的生成树中一定要包含G的所有顶点D．连通图G的生成树一定是连通而且不包含回路21．散列查找的原理是（A）。A．在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系B．按待查记录的关键字有序的顺序方式存储C．按关键字值的比较进行查找D．基于二分查找的方法22．有序表为{1，2，4，6，10，18，20，32}，用课本中折半查找算法查找值18，经（B）次比较后成功查到。A．3B．2C．4D．523．排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是(A)。A．直接插入排序B．快速排序C．冒泡排序D．选择排序24．在排序过程中，可以通过某一趟排序的相关操作所提供的信息，判断序列是否已经排好序，从而可以提前结束排序过程的排序算法是(A)。A．冒泡B．选择C．直接插入D．折半插入25．采用顺序查找法对长度为n的线性表进行查找（不采用表尾设监视哨的方法），最坏的情况下要进行（B）次元素间的比较。A．n+2B．nC．n-1D．n/226．用折半查找法，对长度为12的有序的线性表进行查找，最坏情况下要进行（A）次元素间的比较A．4B．3C．5D．627．如图若从顶点a出发按广度优先搜索法进行遍历，则可能得到的顶点序列为（D）。A．acebdfghB．aebcghdfC．aedfbcghD．abecdfgh图128．如图若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（B）。A．acfgedbB．aedbgfcC．acfebdgD．aecbdgf29．一棵哈夫曼树总共有23个结点，该树共有（D）个叶结点（终端结点）A．10B．13C．11D．1230．一棵哈夫曼树总共有25个结点，该树共有（A）个非叶结点（非终端结点）。A．12B．13C．14D．1531．针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用（D）存储方式最节省时间。A．单链表B．双链表C．单循环链表D．顺序表32．线性表采用链式存储时，其地址（C）。A．一定是不连续的B．必须是连续的C．可以连续也可以不连续D．部分地址必须是连续的33．数据结构中，与所使用的计算机无关的是数据的（D）结构。A．物理B．存储C．逻辑与物理D．逻辑34．带头结点的单向链表的头指针为head，该链表为空的判定条件是（C）的值为真。A．head==NULLB．head->next==headC．head->next==NULLD．head==head->next35．以下特征中，（D）不是算法的特性。A．有穷性B．确定性C．可行性D．有0个或多个输出36．设顺序存储的线性表长度为n，对于插入操作，设插入位置是等概率的，则插入一个元素平均移动元素的次数为（A）。A．n/2B．nC．n-1D．n-i+137．设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（A）。A．n-i+1B．n-iC．n-i-1D．i38．一个栈的进栈序列是5，6，7，8，则栈的不可能的出栈序列是（A）（进出栈操作可以交替进行）A．5，8，6，7B．7，6，8，5C．7，6，5，8D．8，7，6，539．栈的插入删除操作在（D）进行。A．栈底B．任意位置C．指定位置D．栈顶40．栈和队列的相同点是（D）。A．都是后进先出B．都是后进后出C．逻辑结构与线性表不同D．逻辑结构与线性表相同，都是操作规则受到限制的线性表41．以下说法正确的是（C）。A．栈的特点是先进先出，队列的特点是先进后出B．栈和队列的特点都是先进后出C．栈的特点是先进后出，队列的特点是先进先出D．栈和队列的特点都是先进先出42．在C语言中，利用数组a存放字符串“Hello”，以下语句中正确的是（A）。A．chara[10]=“Hello”;B．chara[10];a=“Hello”;C．chara[10]=‘Hello’;D．chara[10]={‘H’,’e’,’l’,’l’,’o’};43．元素2，4，6，8按顺序依次进栈，则该栈的不可能输出序列是（D）（进栈出栈可以交替进行）。A．8，6，4，2B．2，4，6，8C．4，2，8，6D．8，6，2，444．设有一个15阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩阵A的第一个元素为a1,1，数组b的下标从1开始），则数组元素b[13]对应A的矩阵元素是（A）。A．a5,3B．a6,4C．a7,2D．a6,845．设有一个15阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a7,6在一维数组B中的下标是（C）。A．42B．13C．27D．3246．一棵完全二叉树共有30个结点，则该树一共有（D）层(根结点所在层为第一层)。A．6B．4C．3D．547．串函数StrCmp（“d”，“D”）的值为（B）。A．0B．1C．-1D．348．以下说法正确的是（D）。A．连通图G的生成树中不一定包含G的所有顶点B．连通图G的生成树中一定要包含G的所有边C．连通图G的生成树一定是唯一的D．连通图G一定存在生成树49．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（D）。A．2iB．2i-1C．2i+2D．2i+150．对二叉排序树进行（C）遍历，遍历所得到的序列是有序序列。A．按层次B．前序C．中序D．后序51．设一棵有n个结点采用链式存储的二叉树，则该树共有（D）个指针域为空。A．2nB．2n+1C．2n+2D．n+152．以下排序算法中，在一趟排序过程中，除了其它相关操作外，只进行一次元素间的交换的算法是（A）。A．直接选择B．冒泡C．直接插入D．折半插入53．已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（B）。A．abcedfB．abcefdC．aebcfdD．acfdeb图154．对长度为n的线性表进行顺序查找，在等概率情况下，平均查找长度为（B）。A．nB．（n+1）/2C．2nD．n-155．在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86时，经（D）次比较后查找成功。A．6B．3C．8D．456．如图若从顶点a出发按深度优先搜索法进行遍历，则可能得到的顶点序列为（A）。A．acfgedbB．aedcbgfC．acfebdgD．aecbdgf57．有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（A）。A．29/10B．31/10C．26/10D．29/958．一棵哈夫曼树有12个叶子结点（终端结点），该树总共有（C）个结点。A．22B．21C．23D．2459．一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（A）。A．31，29，37，47，70，85B．29，31，37，47，70，85C．31，29，37，70，47，85D．31，29，37，85，47，7060．队列的删除操作在（A）进行。A．队头B．队尾C．队头或队尾D．在任意指定位置61．（A）是性质相同的数据元素的集合，是数据的子集。A．数据对象B．数据元素C．数据结构D．数据项62．设链表中的结点是NODE类型的结构体变量，且有NODE*p；为了申请一个新结点，并由p指向该结点，可用以下语句（D）。A．p=(NODE*)malloc(sizeof(p));B．p=(*NODE)malloc(sizeof(NODE));C．p=(NODE)malloc(sizeof(p));D．p=(NODE*)malloc(sizeof(NODE));63．设顺序存储的线性长度为n，要在第i个元素之前插入一个新元素，按课本的算法当i=(C）时，移动元素次数为2A．n/2B．nC．n-1C．164．一个栈的进栈序列是1，2，3，4，则栈的不可能的出栈序列是（D）（进出栈操作可以交替进行）A．3，2，4，1B．3，2，1，4C．4，3，2，1D．1，4，2，365．设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成，front和rear分别为链队列的头指针和尾指针。设p指向要入队的新结点(该结点已被赋值)，则入队操作为（A）。A．rear->next=p;rear=p;B．rear->next=p;p=rear;C．p=rear->next;rear=p;D．rear=p;rear->next=p;66．以下说法不正确的是（D）。A．顺序栈中，栈满时再进行进栈操作称为“上溢”B．顺序栈中，栈空时再作出栈栈操作称为“下溢”C．顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空D．顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满67．设有一个20阶的对称矩阵A，采用压缩存储方式，将其下三角部分以行序为主序存储到一维数组中（矩阵A的第一个元素为a11，数组b的下标从1开始），则矩阵元素a8,5在一维数组b中的下标是（D）。A．30B．28C．40D．3368．已知一个图的所有顶点的度数之和为m，则m一定不可能是（D）。A．4B．8C．12D．969．以下说法正确的是（C）。A．连通图G的生成树中可以包含回路B．连通图G的生成树可以是不连通的C．连通图G的生成树一定是连通而不包含回路的D．连通图G的生成树一定是唯一的70．对n个元素进行冒泡排序，通常要进行n-1趟冒泡，在第j趟冒泡中共要进行（C）次元素间的比较。A．jB．j-1C．n-jD．n-j-171．在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是（C）。A．冒泡B．选择C．折半插入D．直接插入72．一棵哈夫曼树有n个叶子结点（终端结点），该树总共有（B）个结点。A．2n-2B．2n-1C．2nD．2n+273．数据的（A）结构与所使用的计算机无关。A．逻辑B．物理C．存储D．逻辑与存储74．从n个数中选取最大元素（B）。A．基本操作是数据元素间的交换B．算法的时间复杂度是O(n)C．算法的时间复杂度是O(n2)D．需要进行(n+1)次数据元素间的比较75．设head为非空的单向循环链表头指针，p指向链表的尾结点，则满足逻辑表达式（B）的值为真。A．p->next=NULLB．p->next==headC．p->next=headD．p==NULL76．设顺序存储的线性表长度为n，要删除第i个元素，按课本的算法，当i=（C）时，移动元素的次数为3。A．3B．n/2C．n-3D．377．一个栈的进栈序列是a，b，c，d，则栈的不可能的出栈序列是（D）。A．dcbaB．bcadC．cbadD．adbc78．设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成，front和rear分别为链队列的头指针和尾指针，要执行出队操作，用x保存出队元素的值，p为指向结点类型的指针，可执行如下操作：p=front->next;x=p->data;然后指行（D）。A．front=p->next;B．front->next=p;C．front=p;D．front->next=p->next;79．在C语言中，存储字符串“ABCD”需要占用（C）字节。A．4B．2C．5D．380．设有一个10阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩阵A的第一个元素为a1,1，数组b的下标从1开始），则矩阵元素a5,3对应一维数组b的数组元素是（C）。A．b[18]B．b[8]C．b[13]D．b[10]81．设有一个15阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩阵A的第一个元素为a1,1，数组b的下标从1开始），则数组元素b[13]对应A的矩阵元素是（A）。A．a5,3B．a6,4C．a7,2D．a6,882．深度为5的完全二叉树共有20个结点，则第5层上有（C）个结点(根所在结点为第一层)。A．3B．8C．5D．683．已知一个图的所有顶点的度数之和为m，且m是以下4中情况之一，则m只可能是（D）。A．9B．7C．15D．884．以下说法正确的是（C）。A．连通图G的生成树中不一定包含G的所有顶点B．连通图G的生成树中一定要包含G的所有边C．连通图G一定存在生成树D．连通图G的生成树一定是唯一的85．线性表只要以（C）方式存储就能进行折半查找。A．链接B．顺序C．关键字有序的顺序D．二叉树86．对二叉排序树进行（C）遍历，遍历所得到的序列是有序序列。A．按层次B．前序C．中序D．后序87．对n个元素进行冒泡排序若某趟冒泡中只进行了（C）次元素间的交换，则表明序列已经排好序。A．1B．2C．0D．n-188．在对一组元素（64，48，106，33，25，82，70，55，93）进行直接插入排序时，当进行到要把第7个元素70插入到已经排好序的子表时，为找到插入位置，需进行（C）次元素间的比较（指由小到大排序）。A．6B．2C．3D．489．如图，若从顶点a出发按广度优先搜索法进行遍历，则可能得到的顶点序列为（C）。A．acebdgfB．acfedgbC．abecdgfD．abecfdg90．一棵哈夫曼树有10个非叶子结点（非终端结点），该树总共有（A）个结点。A．21B．20C．22D．1991．一棵哈夫曼树有12个叶子结点（终端结点），该树总共有（C）个结点。A．21B．22C．23D．2492．队列的插入操作在（B）进行。A．队头B．队尾C．队头或队尾D．在任意指定位置93．队列的删除操作在（B）进行。A．队尾B．队头C．队头或队尾D．在任意指定位置94．链表所具备的特点是（C）。A.可以随机访问任一结点B.占用连续的存储空间C.插人删除元素的操作不需要移动元素结点D.可以通过下标对链表进行直接访问95．线性结构中数据元素的位置之间存在(C)的关系。A.一对一B.一对多C.多对多D.每一个元素都有一个直接前驱和一个直接后继96．算法的时间复杂度与(C)有关。A.所使用的计算机B.与计算机的操作系统C.与算法本身D.与数据结构97．4.在一个单链表中，p,q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用的语句是()。A.p=q->riextB.p->next=qC.p->next=q->nextD.q->next=NULL98．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为(C)A.r=f->next;B.r=r->next;C.f=f->next;D.f=r->next;99.元素3,6,9按顺序依次进栈，则该栈的不可能输出序列是(B)(进栈出栈可以交替进行)A.9，6，3B.9，3，6C.6，3，9D.3，9，6100．设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组B中(数组下标从1开始)，则矩阵中元素戊.s在一维数组B中的下标是()A.33B.32C.85D.41101．排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列(初始为空)的一端的方法，称为(D)排序。A.归并B.插人C.快速D.选择102．排序算法中，从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较(要求比较次数尽量少)，然后将其放入已排序序列的正确位置的方法是(C)。A.冒泡B.直接插入C.折半插入D.选择排序二、填空题1．通常数据的逻辑结构包括集合、__线性__、_树形__、图状__四种类型。2．通常可以把一本含有不同章节的书的目录结构抽象成___树形_结构。3．设有一个单向链表，结点的指针域为next，头指针为head，p指向尾结点，为了使该单向链表改为单向循环链表，可用语句___p->next=head;_____。4．要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点，若链表中结点的指针域为next，可执行_s->next=p->next；___和p->next=s;的操作。5．设有一个单向循环链表，头指针为head，链表中结点的指针域为next，p指向尾结点的直接前驱结点，若要删除尾结点，得到一个新的单向循环链表，可执行操作__p->next=head；。6．设有一个非空的链栈，栈顶指针为hs，要进行出栈操作，用x保存出栈结点的值，栈结点的指针域为next，则可执行x=hs->data;___hs=hs->next;__。7．在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next，则插入一个s所指结点的操作为__r->next=s_；r=s；8．在一个不带头结点的非空链队中，f和r分别为队头和队尾指针，队结点的数据域为data，指针域为next，若要进行出队操作，并用变量x存放出队元素的数据值，则相关操作为x=f->data;f=f->next;。9．循环队列的队头指针为f，队尾指针为r，当_r==f_时表明队列为空。10．循环队列的最大存储空间为MaxSize=8，采用少用一个元素空间以有效的判断栈空或栈满，若队头指针front=4，则当队尾指针rear=_4_时，队列为空，当rear=__2___时，队列有6个元素。11．稀疏矩阵存储时，采用一个由__行号__、___列号_、__非零元__3部分信息组成的三元组唯一确定矩阵中的一个非零元素。12．一棵二叉树没有单分支结点，有6个叶结点，则该树总共有__11___个结点。13．一棵二叉树顺序编号为6的结点（树中各结点的编号与等深度的完全二叉树中对应位置上结点的编号相同），若它存在右孩子，则右孩子的编号为____13____。14．按照二叉树的递归定义，对二叉树遍历的常用算法有__先序_、__中序_、__后序__三种。15．结构中的数据元素存在多对多的关系称为___图状___结构。16．把数据存储到计算机中,并具体体现数据之间的逻辑结构称为__物理（存储）_结构。17．结构中的数据元素存在一对多的关系称为___树形_____结构。18．如图3所示的二叉树，其后序遍历序列为gdbeihfca。图319．如图4所示的二叉树，其前序遍历序列为___abdefcg__。图420．二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是_____错误_____的。(回答正确或不正确)21．在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针的值增1，当删除一个元素队列时，头指针的值增1。22．根据搜索方法的不同，图的遍历有__深度优先、_广度优先___两种方法。23．循环队列的引入，目的是为了克服假上溢。24．通常可以把某城市中各公交站点间的线路图抽象成_____图状___结构。25．结构中的元素之间存在多对多的关系称为___图状___结构。26．要在一个单向链表中删除p所指向的结点，已知q指向p所指结点的直接前驱结点，若链表中结点的指针域为next，则可执行____q->next=p->next；__。27．设有一个单向循环链表，结点的指针域为next，头指针为head，指针p指向表中某结点，若逻辑表达式___p->next==head;_____的结果为真，则p所指结点为尾结点。28．设有一个链栈，栈顶指针为hs，现有一个s所指向的结点要入栈，则可执行操作_s->next=hs;和hs=s；29．顺序存储字符串“ABCD”需要占用___5__个字节。30．循环队列的最大存储空间为MaxSize=6，采用少用一个元素空间以有效地判断栈空或栈满，若队头指针front=4，当队尾指针rear=____3____时队满，队列中共有____5____个元素。31．一棵二叉树叶结点（终端结点）数为5，单分支结点数为2，该树共有__11____个结点32．设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10，该完全二叉树一共有_____21___个结点。33．一棵二叉树中顺序编号为5的结点（树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同），若它存在左孩子，则左孩子的编号为____10____。34．结构中的数据元素存在一对一的关系称为__线性______结构。35．一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2，则该树共有___2n-1____个结点。36．图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是__正确____的。(回答正确或不正确)37．串的两种最基本的存储方式分别是_顺序存储______和___链式存储_____。38．按某关键字对记录序列排序，若关键字关键字相等的记录的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。39．设有一个不带头结点的单向循环链表，结点的指针域为next，指针p指向尾结点，现要使p指向第一个结点，可用语句_______p=p->next;_。40．要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为next，头指针为head，尾指针为p，，则可执行head=head->next;_____p->next=head；___。41．在双向链表中，每个结点有两个指针域，一个指向_结点的直接后继，另一个指向__结点的直接前驱。42．设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next==NULL,通过操作___p->next=head;__，就可使该单向链表构造成单向循环链表。43．循环队列的最大存储空间为MaxSize，队头指针为f，队尾指针为r，当_（r+1）%MaxSize=f_时表明队列已满。44．从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h->data;和___h=h->next;。(结点的指针域为next)45．程序段intcount=0;char*s=”ABCD”;while(*s!=’\0’){s++;count++;}执行后count=__4_。46．两个串相等的充分必要条件是_串长度相等且对应位置的字符相等。47．一棵二叉树总结点数为11，叶结点数为5，该树有__4__个双分支结点，__2__个单分支结点。48．对二叉树的遍历可分为__先序、中序、后序、层次四种不同的遍历次序。49．设一棵完全二叉树，其最高层上最右边的叶结点的编号为偶数，该叶节点的双亲结点的编号为9，该完全二叉树一共有____18____个结点。50．双向循环链表中，p指向表中某结点，则通过p可以访问到p所指结点的直接后继结点和直接前驱结点，这种说法是__正确______的（回答正确或不正确）。51．栈和队列的操作特点分别是__先进后出（后进先出）_和__先进先出（后进后出）___。52．一棵有14个结点的完全二叉树，则它的最高层上有____7___个结点。53．如图2所示的二叉树，其先序遍历序列为_____abdgcefhi。图254．折半查找只适用于顺序存储结构存储的有序表。55．哈希函数是记录关键字值与该记录___存储地址___之间所构造的对应关系。56．深度为k的二叉树最多有2k-1结点。57．二叉树排序中任一棵子树都是二叉排序树，这种说法是__正确_____的。(回答正确或不正确)58．串的两种最基本的存储方式是___顺序存储_和链式存储__59．结构中的元素之间存在多对多的关系称为_____图状___结构。60．设有一个链栈，栈顶指针为hs，现有一个s所指向的结点要入栈，则可执行操作s->next=hs;_hs=s；。61．循环队列的最大存储空间为MaxSize=6，采用少用一个元素空间以有效地判断栈空或栈满，若队头指针front=4，当队尾指针rear=__3__时队满，队列中共有___5__个元素。62．‘A‘在存储时占__1_个字节。“A”在存储时占__2__个字节。63．程序段char*s=”aBcD”;n=0;while(*s!=’\0’){if(*s>＝’a’&&*s<＝’z’)n++;s++;}执行后n=___2___三、综合题1．（1）已知某二叉树的后序遍历序列是debca，中序遍历序列是dbeac，试画出该二叉树（2）若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系（3）给出该树的前序遍历序列答：（1）（2）d<b<e<a<c（3）abdec2．（1）设head1和p1分别是不带头结点的单向链表A的头指针和尾指针，head2和p2分别是不带头结点的单向链表B的头指针和尾指针，若要把B链表接到A链表之后，得到一个以head1为头指针的单向循环链表，写出其中两个关键的赋值语句（不用完整程序，结点的链域为next）。（2）单向链表的链域为next，设指针p指向单向链表中的某个结点，指针s指向一个要插入链表的新结点，现要把s所指结点插入p所指结点之后，某学生采用以下语句：p->next=s;s->next=p->next;这样做正确吗？若正确则回答正确，若不正确则说明应如何改写答：（1）p1->next=head2；p2->next=head1；（2）不对，s->next=p->next；p->next=s；3．（1）设有一个整数序列{40，28，6，72，100，3，54}依次取出序列中的数，构造一棵二叉排序树（2）对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度答：（1）（2）ASL=（1x1+2x2+3x3+4）/7=18/74．（1）画出对长度为10的有序表进行折半查找的判定树（以序号1，2，……10表示树结点）（2）对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度答：（1）（2）ASL=（1x1+2x2+3x4+4x3）/10=29/105．（1）利用筛选过程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），画出相应的完全二叉树（不要求中间过程）（2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列答：（1）（2）102，52，42，82，16，67，32，576．（1）利用筛选法，把序列{37，77，62，97，11，27，52，47}建成堆（小根堆），画出相应的完全二叉树（2）写出对上述堆所对应的二叉树进行前序遍历得到的序列答：（1）（2）11，37，47，97，77，27，62，527．（1）一组记录的关键字序列为{45，40，65，43，35，95}写出利用快速排序的方法，以第一个记录为基准得到的一趟划分的结果（要求给出一趟划分中每次扫描和交换的结果）（2）同样对序列{45，40，65，43，35，95}利用直接插入排序，写出逐次插入过程（从第一个元素一直到第六个元素）。答：（1）454065433595（2）4045654335953540654335954043456535953540654365953540434565953540434365958．设有一个不带头结点的单向链表，头指针为head，结点类型为NODE，每个结点包含一个数据域data和一个指针域next，该链表有两个结点，p指向第二个结点（尾结点），按以下要求写出相应语句（不要求完整程序，（1）、（2）、（3）、（4）是一个连续的过程）。（1）新开辟一个结点，使指针s指向该结点，结点的数据成员data赋值为1（2）把该结点插入链表的尾部，释放指针s的指向（3）删除链表的第一个结点（4）已知p1指向另一个新结点，把它插入到p所指结点和尾结点之间答：（1）s=（NODE*）malloc(sizeof(NODE));s->data=1;（2）p->next=s;s->next=NULL；free(s)（3）head=head->next；（4）p1->next=p->next；p->next=p1；9．（1）利用筛选过程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），画出相应的完全二叉树（不要求中间过程）（2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列答：（1）（2）102，52，42，82，16，67，32，5710．（1）设有序列{10，12，15，19，22，25，100，130，150，200}画出对上述序列进行折半查找的判定树（以序列中的元素作为树的结点）（2）为了成功查找到100需要进行多少次元素间的比较？为了查找9，经过多少次元素间的比较可知道查找失败？答：（1）（2）4次；3次11．（1）设有一个整数序列{50，38，16，82，110，13，64}，依次取出序列中的数，构造一棵二叉排序树（2）利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到，为了查找15，经多少次元素间的比较可知道查找失败。答：5．（1）（2）三次；四次12．(1)设有查找表{5,14,2,6,18,7,4,16,3},依次取表中数据，构造一棵二叉排序树。（2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。答：(1)(2)中序遍历：中序2，3，4，5，6，7，14，16，1813．（1）已知某二叉树的先序遍历序列是aecdb，中序遍历序列是eadcb，试画出该二叉树（2）给出上述二叉树的后序遍历序列（3）若上述二叉树的各个结点的字符分别是1，2，3，4，5，并恰好使该树成为一棵二叉排序树，试问a、b、c、d、e的值各为多少？答：（1）（2）edbca（3）e=1,a=2,d=3,c=4,b=514．（1）设有一个整数序列{40，28，6，72，100，3，54}依次取出序列中的数，构造一棵二叉排序树（2）对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度答：（1）（2）ASL=（1x1+2x2+3x3+4）/7=18/715．（1）给定数列{8，17，5，9，21，10，7，19，6}，依次取序列中的数构造一棵二叉排序树（2）对上述二叉树给出中序遍历得到的序列答：（1）（2）5，6，7，8，9，10，17，18，19，2116．（1）利用筛选过程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），画出相应的完全二叉树（不要求中间过程）（2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列答：（1）（2）102，52，42，82，16，67，32，5717．（1）以给定权重值1，2，12，13，20，25为叶结点，建立一棵哈夫曼树（2）若哈夫曼树有n个非叶子结点，则树中共有多少结点。对给定的一组权重值建立的棵哈夫曼树是否一定唯一答：（1）（2）2n-1不一定唯一四、程序填空题1．以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格typedefstruct{intkey;……}NODE;intBinary_Search(NODEa[],intn,intk){intlow,mid,high;low=0;high=n-1;while(___low<=high_____){mid=(low+high)/2;if(a[mid].key==k)return__mid)______;elseif(___a[mid].key<k;_____)low=mid+1;else__high=mid-1___;}___return-1____;}2．以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序，完成程序中的空格typedefstruct{intkey;……}NODE;voidselsort(NODEa[],intn){inti,j,k;NODEtemp;for(i=1;i<=__n-1__;i++){k=i;for(j=i+1;j<=___n_____;j++)if(a[j].key<a[k].key)__k=j______;if(i!=k){temp=a[i];___a[i]=a[k]___;____a[k]=temp____;}}}3．以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是链队列的队头、队尾指针structnode{ElemTypedata;structnode*next;};structnode*front，*rear;voidInQueue(ElemTypex){structnode*p;p=(structnode*)___malloc(sizeof(structnode))____;p->data=x;p->next=NULL;___rear->next=p_____;rear=__p_____;}4．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。voidInorder(structBTreeNode*BT){if(BT!=NULL){Inorder(BT->left);printf(“%c”,BT->data);Inorder(BT->right);}}5．以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针structnode{ElemTypedata;structnode*next;};structnode*top;voidPush(ElemTypex){structnode*p;p=(structnode*)malloc(___sizeof(structnode)____);p->data=x;___p->next=top_____;_____top=p__;}6．设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。#defineNULL0voidmain(){NODEa,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4;/*d是尾结点*/head=&a;a.next=&b;b.next=&c;c.next=&d;d(next=NULL;/*以上结束建表过程*/p=head;/*p为工作指针，准备输出链表*/do{printf(“%d\n”,p->data);p=p->next;}while(p!=NULL);}7．以下函数在head为头指针的具有头结点的单向链表中删除第i个结点，structnode{intdata;structnode*next;};typedefstructnodeNODEintdelete(NODE*head,inti){NODE*p,*q;intj;q=head;j=0;while((q!=NULL)&&(___j<i-1_____)){___q=q->next_____;j++;}if(q==NULL)return(0);p=__q->next____;___q->next__=p->next;free(__p_);return(1);}8．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。voidInorder(structBTreeNode*BT){if(BT!=NULL){Inorder(BT->left);printf(“%c”,BT->data);Inorder(BT->right);}}abecdhgfbcgdafebdfecaabecdfgabecdfgefgibachdgfabdecefgibachdabced4028723100546528496310711642325257678210242826752573216102初始树堆初始树堆377762475227119711372747526277971642325257678210242826752573216102初始树堆221213019150251520010010503882131106416246167318514aecbd402872310054685176219719101642325257678210242826752573216102初始树堆2845132135732091315250123211