一、选择题（每题2分共20分）
1．若长度为n的线性表(a1, a2,…, an)采用顺序存储，删除它的第i个数据元素，需要依次向前移动    个数据元素。
    A. n-i          B.    n+i        C.n-i+1          D.n-i-1
2． 在一个单链表head中，若要在指针p所指结点后插入一个q指针所指结点，则执行_____。
A. p->next=q->next; q->next=p;
B. q->next=p->next; p=q;
C. p->next=q->next; p->next=q;
D. q->next=p->next; p->next=q;
3．栈是一种          的线性表。
A. 只允许在一端进行插入和在另一端进行删除
    B. 只允许在一端进行插入和删除
    C. 只允许在两端进行插入和删除
中级会计查成绩    D. 允许在中间部位进行插入和删除
4．算术表达式a×b+c/d的逆波兰式是______。 
  A. ab×cd+/    B. ab×c/d+      C. ab×cd/+        D. ab+×cd/
5．循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。
A．(rear-front+m)%m            B．read-front+1
C．read-front-1                    D．read-front
6．设二维数组a[0…m-1][0…n-1]按行优先顺序存储在首地址为loc(a00)的存储区域中，每
个元素占d个单元，则aij的地址为________。
A. loc(a00) +( i×n+ j) ×d            B. loc(a00) +(j×m+i) ×d
C. loc(a00) +((j-1)×n+i-1) ×d          D. loc(a00) +((j-1)×m+i-1) ×d
7．对于二叉树来说,第i层上至多有____个结点。
        A．2i        B． 2i-1        C．2i-1      D．2i-1-1
8．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当二分查值为82的结点时，（ ）次比较后查成功。
A．1      B．2        C．4        D．8
9．设哈希表长m=11，哈希函数H（key）=key%11。表中已有4个结点：addr（15）=4， addr（38）=5，addr（61）=6，addr（84）=7，其余地址为空，如果线性探测再散列处理冲突，关键字为49的结点地址是      。
  A．3          B．5        C．8      高考大专分数线 D．9
10．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下：
25,84,21,47,15,27,68,35,20
15,84,21,47,25,27,68,35,20
15,20,21,47,25,27,68,35,84
重庆人才招聘市场
15,20,21,25,47,27,68,35,84
        ．
        ．
15,20,21,25,27,35,47,68,84
则采用的排序方法是（ ）。
A．冒泡排序        B．快速排序      C．归并排序          D．选择排序
二、求解题
1．已知二叉树的扩展前序序列：FKHφφBEφφφGAφφDφCφφ.请画出该二叉树并写出该树的中序和后序序列。（12分）
2．画出下列树对应的二叉树。（10分）
3.给定无向图G=<V,E>,其中V={a,b,c,d,e},E={(a,b),(a,e),(b,e),(b,c),(c,e),(e,d)}.财政部会计资格评价请画出图G的邻接矩阵,邻接表。从结点a出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。(12分)
4．从空的二叉排序树开始依次插入30，18,11,17,7,5,13,41,29,37,23,19。画出该二叉排序浙江省公务员考试网2023
树。（9分）
5．分别写出对序列 10,18,11,17,7,5,13,41,29,37,23,19,25进行快速排序和冒泡排序的过程。(16分)
三、写出下列算法的功能或输出结果
1.typedef struct List         
  { int number;
    struct List *next;
  } Node，*Link;
void func1(Link p)//p指向单链表
{
while(p!=NULL)
  { printf(“%d\n”,p->number);
p=p->next;
}
}
功能是                              。
2.写出下列程序段的运行结果（栈中的元素类型是char）：
main(　)
{    SEQSTACK s,*p;
      char x, y;
      p = &s;
      initstack(p);
      x = ‘c’; y = ‘k’;
      push(p,x); push(p,’a′); push(p,y);
      x = pop(p);
      push(p,’t′); 
      push(p,’s′);
      while(!empty(p))
        {  y = pop(p);
            printf(″%c″,y);}
      printf(″%c＼n″,x);
}
运行结果是                      。   
3．int func3 (int r[ ],  int n,  int k) 
云南人力资源和社会保障网人事考试专栏{ int i,low=0, high=n-1, mid, find=0;
    while (low<=high &&find==0)
      { mid=(low+high)/2;
      if (k<r[mid])  high=mid-1;
      else  if (k>r[mid])  low=mid+1;
else  ｛i＝mid;
find=1;｝
}
if (!find) return -1;
return i;
}
功能是                               。
四、读程填空
1．下列算法创建n个元素的带头单链表.
typedef struct lnode                       
        { int  data;
          struct lnode *next;
          }lnode,*linklist ;
void  create(linklist &head, int n) 
  {linklist p; int i;
  head=(linklist)malloc(sizeof(lnode));
        A      ; 
  for(i=n;i>0;i--)
{p =(linklist)malloc(sizeof(lnode));
scanf(“%d”,&p->data);
      B      ;
      C      ;
}
  }
2．完成下列插入排序算法。
typedef struct node
{int key;
int data;
}NODE;
void insert(NODE r[ ],int n) // r[0]为哨兵
{int i,j;
for(i=2;i<=n;i++)
  if (    A      )
  {r[0]=r[i];j=i-1;
while (      B      )
    r[j+1]=r[j--];
      C      ;
}
}
参考答案
一、A  D B  C  A  A  B  C  C  D