数据结构填空题集锦
数据结构填空题集锦
一
1. 数据结构是指数据及其相互之间的联系。当结点之间存在M对N（M：N）的联系时，称这种结构为图或者是图的结构
2. 队列的插入操作是在队列的尾进行，删除操作是在队列的首进行。
3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是top==0 （要超出才为满）。
4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为O(1) ，在表尾插入元素的时间复杂度为O(n) 。
5. 设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用128 个字节。W中第6 行的元素和第4 列的元素共占用44 个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为108 。
6.广义表A= (a,(a,b),((a,b),c)),则它的深度为3 ，它的长度为3 。
7. 二叉树是指度为2的有序树。一棵结点数为N的二叉树，其所有结点的度的总和是n-1 。
8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个有序序列有序列表。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的_后缀表达式后缀表达式（或列波兰式）。
9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为___2n___个，其中____n-1___个用于指向孩子，___n+1____个指针是空闲的。
10.若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A 中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为_2加一___,右孩子元素为_2加二___，双亲元素为__（i-1）/2__。
11.在线性表的散列存储中，处理冲突的常用方法有开放地址法和__ _链接法______两种。
12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用快速_排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用____并归排序。
1. 通常从四个方面评价算法的质量：正确性、易读性、强壮性和高效性。
2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_O（n）。
3. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__9__个，树的深度为_3__，树的度为___3__。
4. 后缀算式9 2 3 +- 10 2 / -的值为_-1__。中缀算式（3+4X）-2Y/3对应的后缀算式为__3 4 X * 2 Y * 3 / -______。
5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有___2n_____个指针域，其中有__n-1______个指针域是存放了地址，有___n+1____个指针是空指针。
6. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有__e_____个和__2e______个。
7. AOV网是一种有向无回路的图。
8. 在一个具有n个顶点的无向完全图中，包含有__n(n-1)/2______条边，在一个具有n个顶点的有向完全图中，包含有_n(n-1)___条边。
9. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____
(12,40)____、_( )______、_(_74)____和___(23,55,63)_____。
10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___增加1________。
11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_O（log2 n）_，整个堆排序过程的时间复杂度为_O（nlog2 n）__。
12. 在快速排序、堆排序、归并排序中，归并排序是稳定的。
1、数据的逻辑结构被分为_集合_____、_线性___ 、___树_____和___图_____四种。
2、一种抽象数据类型包括___数据描述和操作声明两个部分。
3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为__（38，56，25，60，42，74）____。
4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为_______ HL→next =NULL ____和______ HL=HL→next；_____。
5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的____前一个位置_______，该循环队列的最大长度为_____n-1_____。
6、当堆栈采用顺序存储结构时，栈顶元素的值可用S.stack [S.top] 表示；当堆栈采用链接存储结构时，栈顶元素的值可用__ HS→data _表示。
7、一棵高度为5的二叉树中最少含有_____5____个结点，最多含有____31____个结点；
8、在图的邻接表中，每个结点被称为____边结点________，通常它包含三个域：一是__邻接点域__；二是___权域________；三是___链域___。
9、在一个索引文件的索引表中，每个索引项包含对应记录的___索引值域______和___开始位置域________两项数据。
10、假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J））），则树中所含的结点数为____10_____个，树的深度为____3_____,树的度为_____3___, 结点H的双亲结点为___b _____,孩子结点为____i和J___________ 。
11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O（log2n）__,整个堆排序过程的时间复杂度为___ O(nlog2n)__。
12、在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于___M___个，则必须把它分裂为___M-1____个结点。
16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储（或存储结构）无关，是独立于计算机的。
17．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head 可用p表示为head= p－＞next－＞next 。
18．栈顶的位置是随着进栈和退栈操作而变化的。
19．在串S=“structure”中，以t为首字符的子串有12 个。
20．假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B[0]存储矩阵中第1个元素a1,1,则B[31]中存放的元素是a4,8。
21．已知一棵完全二叉树中共有768结点，则该树中共有384 个叶子结点。
22．已知一个图的广度优先生成树如右图所示，则与此相
应的广度优先遍历序列为。
23．在单链表上难以实现的排序方法有快速排序和堆排序, 希尔排序。24．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 2 。
25．多重表文件和倒排文件都归属于多关键字文件。
1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____(F+1) % m ________;。
2. 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为______ O(n)_____，在链式存储结构上实现顺序查找的平均时间复杂度为____ O(n)______。
3. 设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有___2n _____个指针域，n+1
个空指针域。
4. 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为______s->next=p->next; s->next=s __。
5. 设无向图G中有n个顶点和e条边，则其对应的邻接表中有____n_____个表头结点和_____2e____个表结点。
6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有__m=2e____关系。
7. 设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__cba________。
8. 设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是_____4______，编号为8的左孩子结点的编号是_____16________。
9. 下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。int index(char s[ ], char t[ ])
{
i=j=0;
while(i if (j==strlen(t))return(i-strlen(t));else return (-1); } 10. 设一个连通图G中有n个顶点e条边，则其最小生成树上有___n-1_____条边。 1. 为了能有效地应用HASH查找技术，必须解决的两个问题是___构造一个好的HASH 函数____和________确定解决冲突的方法______。 2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。 typedef struct {int s[100]; int top;} sqstack; void push(sqstack &stack,int x) { if (stack.top==m-1) p rintf(“overflow”); 1.else {___ stack.top++___;____ stack.s[stack.top]=x _____;} } 3. 中序遍历二叉排序树所得到的序列是___有序________序列（填有序或无序）。 4. 快速排序的最坏时间复杂度为____ O(n2)_______，平均时间复杂度为___ O(nlog2n)_______。 5. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为___N0-1______；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有__2N0+N1_____个空指针域。 2. 6. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=__d/2_。 7. 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为__________(31，38，54，56，75，80，55，63)____ ____。 8. 设某无向图G的邻接表为 3 1 2 4 1 3 1 4 2 3 4 3 2 1 > - > - > - > - > - > - > - > - > - > - v v v v ，则从顶点V1开始的深度优先遍历序列 为____(1，3，4，2)_______；广度优先遍历序列为___(1，3，2，4)_________。 七 1.数据的物理结构主要包括_____顺序存储结构____和___链式存储结构___两种情况。 2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为___9___；若用二叉链表作为该完全二叉树的存储结构，则共有____501_____个空指针域。 3. 设输入序列为1、2、3，则经过栈的作用后可以得到____5___种不同的输出序列。 4. 设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的__出度______，第i列上所有元素之和等于顶点i的__入度______。 5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有__0__个度数为1的结点。 6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_____e=d____。 7. _____中序_____遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。 8. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较____7____次就可以断定数据元素X是否在查找表中。 9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_____O(1)_______。 10. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为i/2___，右孩子结点的编号为2i+1 。 11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为(5，16，71，23，72，94，73 。 12. 设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为(1，4，3，2)。 13. 下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。struct record{int key; int others;}; int hashsqsearch(struct record hashtable[ ],int k) { int i,j; j=i=k % p; while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(_j+1___) %m; if (i==j) return(-1);} if (____hashtable[j].key==k _______ ) return(j); else return(-1); } 14. 下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree; bitree *bstsearch(bitree *t, int k) { if (t==0 ) return(0);else while (t!=0) if (t->key==k)____ return(t) else if (t->key>k) t=t->lchild; else__ t=t->rchild ___; } 1．设有n个无序的记录关键字，则直接插入排序的时间复杂度为__ O(n2)______，快速排序的平均时间复杂度为___ O(nlog2n)______。 2．设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_____ p>llink->rlink=p->rlink; p->rlink->llink=p->rlink_____（设结点中的两个指针域分别为llink和rlink）。 3．根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____3__。 4．深度为k的完全二叉树中最少有___2k-1__个结点。 5．设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第_n/2___个元素开始进行筛选。 6．设哈夫曼树中共有99个结点，则该树中有___50___个叶子结点；若采用二叉链表作为存储结构，则该树中有__51___个空指针域。 7．设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储__ m-1______个队列元素；当前实际存储__(R-F+M)%M ____个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。 8．设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中__n+1-i _____个数据元素；删除第i个位置上的数据元素需要移动表中__ n-i _个元素。 9．设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为_____(19，18，16，20，30，22)_____。 10．设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为________(16，18，19，20，32，22) 。 11．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j 互为邻接点的条件是_____ A[i][j]=1_____。 12．设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数__等于_第i列上非0元素的个数（填等于，大于或小于）。 13．设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____ BDCA ________。 14．设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。 typedef struct node {int key; struct node *next;} lklist; void createlkhash(lklist *hashtable[ ]) { int i,k; lklist *s; for(i=0;i for(i=0;i { s=(lklist *)malloc(sizeof(lklist)); s->key=a[i]; k=a[i] % p; s->next=hashtable[k];______ hashtable[k]=s _________________; } } 1. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是___top1+1=top2__________。 2. 在图的邻接表中用顺序存储结构存储表头结点的优点是____可以随机访问到任一个顶点的简单链表_______。 3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有__i(i+1)/2+j-1_____个数据元素。 4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为____ FILO ______表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为____ FIFO _____表。 5. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为____ ABDECF _______，中序遍历序列为____ DBEAFC _______，后序遍历序列为______ DEBFCA _____。 6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为___8_____，有____64______个叶子结点。 7. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的____出度____，第i列中所有非零元素个数之和等于顶点i的___入度___。 8. 设一组初始记录关键字序列(k1，k2，……，kn)是堆，则对i=1，2，…，n/2而言满足的条件为__k i<=k2i && k i<=k2i+1__________________________。 9. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。 void bubble(int r[n]) { for(i=1;i<=n-1; i++) { for(exchange=0,j=0; j<_____n-i ________;j++) if (r[j]>r[j+1]){temp=r[j+1];_____ r[j+1]=r[j]_________;r[j]=temp;exchange=1;} if (exchange==0) return； } } 10. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。 struct record{int key; int others;}; int bisearch(struct record r[ ], int k) { int low=0,mid,high=n-1; while(low<=high) { ______mid=(low+high)/2_________; if(r[mid].key==k) return(mid+1); else if(__r[mid].key>k ___) high=mid-1;else low=mid+1; } return(0); } 1．for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为___ O(n)______。 2．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为_______ s->next=p->next; p->next=s _____（设结点的指针域为next）。3．设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列___(1，3，2，4，5)_______。 4．设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是__n-1_______。 5．设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有___129____个结点数。 6．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为___ F==R _____。 7．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是__________p->lchild==0&&p->rchild==0________。 8．简单选择排序和直接插入排序算法的平均时间复杂度为_____O(n2)______。 9．快速排序算法的空间复杂度平均情况下为____O(nlog2n)______，最坏的情况下为__ O(n) 。 10.散列表中解决冲突的两种方法是____开放定址法_________和_____链地址法________。 十一 1. 设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为__ s->left=p _______=p；s->right=p->right；___ p->right _______=s；p->right->left=s；（设结点中的两个指针域分别为left和right）。 2. 设完全有向图中有n个顶点，则该完全有向图中共有__ n(n-1)______条有向条；设完全无向图中有n个顶点，则该完全无向图中共有___ n(n-1)/2_____条无向边。 3. 设关键字序列为(Kl，K2，…，Kn)，则用筛选法建初始堆必须从第___n/2___个元素开始进行筛选。 4. 解决散列表冲突的两种方法是______开放定址法____和____链地址法_____。 5. 设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有__14____个。 6. 高度为h的完全二叉树中最少有___2h-1___个结点，最多有__2h-1___个结点。 7. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是______(12，24，35，27，18，26)____________________________。 8. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果的是__________(12，18，24，27，35，26)__________。 9. 设一棵二叉树的前序序列为ABC，则有_____5_________种不同的二叉树可以得到这种序列。 10. 下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。 struct record {int key;datatype others;}; void quickpass(struct record r[], int s, int t, int &i) { int j=t; struct record x=r[s]; i=s; while(i { while (i while (____i } ___ r[i]=x _____; } 十二 1．设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为____(49，13，27，50，76，38，65，97)_______ ___。 2．下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。 typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree; void bstinsert(bitree *&t,int k) { if(t==0){____t=(bitree )malloc(sizeof(bitree)) ____;t->data=k;t->lchild=t->rchild=0;} else if (t->data>k) bstinsert(t->lchild,k);else___ bstinsert(t->rchild,k)____ ___; } 3．设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next; ____ p->next=s _____________;。4．设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=___head->rlink ______和head=_____ p->llink _____（设结点中的两个指针域分别为llink和rlink）。 5．设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为___ CABD _______。 6．完全二叉树中第5层上最少有___1___个结点，最多有___16______个结点。 7．设有向图中不存在有向边 8．设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为___(13，27，38，50，76，49，65，97)__ ______。 9．设连通图G中有n个顶点e条边，则对应的最小生成树上有_____ n-1______条边。10．设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与___50___相互交换即可。 十三 1．设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为： 1) s->next=____p->next _______；2) p->next=s；3) t=p->data； 4) p->data=____ s->data _______；5) s->data=t； 2．设某棵完全二叉树中有100个结点，则该二叉树中有_____50_________个叶子结点。3．设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储___ m-1____队列元素。4．对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为___6_______，在整个排序过程中最多需要进行_____8_____趟排序才可以完成。 5．在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择____快速_____排序，如果从节省存储空间的角度来考虑则最好选择__堆______排序。 6．设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是______19/7________。 7．设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为_______CBDA__________。 8．设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为____6___。9．设一组记录关键字序列为(80，70，33，65，24，56，48)，则用 筛选法建成的初始堆为__(24，65，33，80，70，56，48)______ __。 10．设无向图G（如右图所示），则其最小生成树上所有边的权值之 和为_____8_____。 十四 1. 设需要对5个不同的记录关键字进行排序，则至少需要比较____4_________次，至多需要比较____10_________次。 2. 快速排序算法的平均时间复杂度为____ O(nlog2n)________，直接插入排序算法的平均时间复杂度为____ O(n2)_______。 3. 设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较___n______次。 4. 设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有____1_____个，比较两次查找成功有结点数有_____2____个。 5. 设一棵m叉树脂的结点数为n，用多重链表表示其存储结构，则该树中有__n(m-1)+1___个空指针域。 6. 设指针变量p指向单链表中结点A，则删除结点A的语句序列为： q=p->next；p->data=q->data；p->next=___ q->next______；feee(q)； 7. 数据结构从逻辑上划分为三种基本类型：__线性结构____、_树型结构__和_图型结构__。 8. 设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为___ O(n2)______；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为____ O(n+e)_____。 9. 设散列表的长度为8，散列函数H(k)=k % 7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是__8/3______。 10. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为___(38，13，27，10，65，76，97)__________________。 11. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为_(10，13，27，76，65，97，38)_____________________。 12. 设有向图G中的有向边的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，则该图的一个拓扑序列为____124653______________。 13. 下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。 typedef struct node{int data;struct node *lchild;__ struct node *rchild ____;}bitree; void createbitree(bitree *&bt) { scanf(“%c”,&ch); if(ch=='#') ___ bt=0________;else { bt=(bitree*)malloc(sizeof(bitree));bt->data=ch; createbitree(bt->lchild);createbitree(bt->rchild);} } 14. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。 typedef struct node {int data; struct node *next;} lklist; void lklistcreate(____lklist ____ *&head ) { for (i=1;i<=n;i++) { p=(lklist *)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0; if(i==1)head=q=p;else {q->next=p;_ q=p ;} } } 小学少先队组织机构 少先队组织由少先队大队部及各中队组成，其成员包括少先队辅导员、大队长、中队长、小队长、少先队员，为了健全完善我校少先队组织，特制定以下方案： 一、成员的确定 1、大队长由纪律部门、卫生部门、升旗手、鼓号队四个组织各推荐一名优秀学生担任（共四名），该部门就主要由大队长负责部门内的纪律。 2、中、小队长由各班中队公开、公平选举产生，中队长各班一名（共11名），一般由班长担任，也可以根据本班的实际情况另行选举。小队长各班各小组先选举出一名（共8个小组，就8名小队长）然后各班可以根据需要添加小队长几名。 3、在进行班级选举中、小队长时应注意，必须把卫生、纪律部门的检查学生先选举在中、小队长之内，剩余的中、小队长名额由班级其他优秀学生担任。 4、在班级公开、公平选举出中、小队长之后，由班主任老师授予中、小队长标志，大队长由少先队大队部授予大队长标志。 二、成员的职责及任免 1、大、中、小队长属于学校少先队组织，各队长不管是遇见该班的、外班的，不管是否在值勤，只要发现任何人在学校内出现说脏话、乱扔果皮纸屑、追逐打闹、攀爬栏杆、乱写乱画等等一些违纪现象，都可以站出来制止或者报告老师。 2、班主任在各中队要对中、小队长提出具体的责任，如设置管卫生的小队长，管纪律的小队长，管文明礼貌的、管服装整洁的等等，根据你班的需要自行定出若干相应职责，让各位队长清楚自己的职权，有具体可操作的事情去管理，让各位队长成为班主任真正的助手，让学生管理学生。各中队长可以负责全班的任何违纪现象，并负责每天早上检查红领巾与校牌及各小队长标志的佩戴情况。 3、大、中、小队长标志要求各队长必须每天佩戴，以身作则，不得违纪，如有违纪现象，班主任可根据中、小队长的表现撤消该同学中、小队长的职务，另行选举，大队长由纪律、卫生部门及少先队大队部撤消，另行选举。 4、各班中、小队长在管理班级的过程中负责，表现优秀，期末评为少先队部门优秀干部。