精华内容
下载资源
问答
  • 数据结构与算法期末考试复习试题
  • 数据结构与算法期末试题试卷A 《数据结构与算法期末试题试卷A 《数据结构与算法期末试题试卷A
  • 数据结构与算法期末试题试卷A 《数据结构与算法期末试题试卷A 《数据结构与算法期末试题试卷A 《数据结构与算法期末试题试卷A 《数据结构与算法期末试题试卷A
  • 数据结构与算法期末练习 一 选择 1以下数据的存储结构无关的术语是 D A循环队列 B. 链表 C. 哈希表 D. 栈 2. 算法的时间复杂度取决于 A A问题的规模 B. 待处理数据的初态 C. A和 B D. 计算机 cpu 3. 一个栈的...
  • 四川大学期末考试试题 2013-2014学年第1学期 课程号 课程名称 数据结构与算法分析A卷 任课教师 适用专业年级 学号 姓名 考试须知 四川大学学生参加由学校组织或由学校承办的各级各类考试必须严格执行四川大学考试...
  • 期末复习数据结构与算法练习

    千次阅读 多人点赞 2020-06-23 19:19:26
    数据结构与算法考试习题第一章 求算法复杂度频率第二章 线性表2.2 填空。2.3何时选用顺序表、何时选用链表作为线性表的存储结构为宜?2.7 已知L是带表头结点的非空单链表,且P结点既不是首元结点,也不是尾元结点...

    数据结构与算法考试习题

    第一章 求算法复杂度与频率

    设n为正整数,试确定下列各程序中前置以记号@的语句的频度和算法复杂度。
    (1) i=1; k=0;
    while( i <= n-1)
    { k+=10*i; @ n-1
    i++;
    }
    分析:T(n)=O(n)

    (2) i=1; k=0;
    do
    { k+=10*i; @ n-1
    i++;
    }while((i<=n-1);
    分析:T(n)=O(n)

    (3) i=1; k=0;
    while(i<=n-1)
    { i++;
    k+=10*i; @ n-1
    }
    分析:T(n)=O(n)

    (4) k=0;
    for(i=1; i<=n; i++){
    for(j=i; j<=n; j++)
    k++; @ n(n+1)/2
    }
    分析: T ( n ) = O ( n 2 ) T(n)= O(n^2) T(n)=O(n2)

    (5) for(i=1; i<=n; i++)
    {
    for(j=1;j<=i; j++)
    {
    for(k=1; k<=j; k++)
    X += delta; @ n(n+1)(n+2)/6
    }
    }
    分析: T ( n ) = O ( n 3 ) T(n)=O(n^3) T(n)=O(n3)

    (6) i=1; j=0;
    while( i+j <= n)
    {
    if(i>j) @ n
    j++;
    else
    i++;
    }
    分析:
      通过分析以上程序段,可将i+j看成一个控制循环次数的变量,且每执行一次循环,i+j的值加1。该程序段的主要时间消耗是while循环,而while循环共做了n次,所以该程序段的执行时间为:T(n)=O(n)

    第二章 线性表

    2.2 填空题。

    (1) 在顺序表中插入或删除一个元素,需要平均移动 元素,具体移动的元素个数与 有关。
    (2) 顺序表中逻辑上相邻的元素的物理位置 紧邻。单链表中逻辑上相邻的元素的物理位置 紧邻。
    (3) 在单链表中,除了首元结点外,任一结点的存储位置由 指示。
    (4) 在单链表中设置头结点的作用是 。

    1、在顺序表中插入或删除一个元素,需要平均移动(表中一半)元素,具体移动的元素个数与(表长和该元素在表中的位置)有关。
    2、顺序表中逻辑上相邻的元素的物理位置(必定)相邻。单链表中逻辑上相邻的元素的物理位置(不一定)相邻。
    3、在单链表中,除了首元结点外,任一结点的存储位置由(其直接前驱结点的链域的值)指示。
    4、在单链表中设置头结点的作用是(插入和删除元素不必进行特殊处理)。

    2.3何时选用顺序表、何时选用链表作为线性表的存储结构为宜?

    答:在实际应用中,应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构,通常有以下几方面的考虑:
     1.基于空间的考虑。当要求存储的线性表长度变化不大,易于事先确定其大小时,为了节约存储空间,宜采用顺序表;反之,当线性表长度变化大,难以估计其存储规模时,采用动态链表作为存储结构为好。
     2.基于时间的考虑。若线性表的操作主要是进行查找,很少做插入和删除操作时,采用顺序表做存储结构为宜;反之, 若需要对线性表进行频繁地插入或删除等的操作时,宜采用链表做存储结构。并且,若链表的插入和删除主要发生在表的首尾两端,则采用尾指针表示的单循环链表为宜。

    2.7 已知L是带表头结点的非空单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。

    a. 删除P结点的直接后继结点的语句序列是____________________。
    b. 删除P结点的直接前驱结点的语句序列是____________________。
    c. 删除P结点的语句序列是____________________。
    d. 删除首元结点的语句序列是____________________。
    

    e. 删除尾元结点的语句序列是____________________。
    (1) P=P->next;
    (2) P->next=P;
    (3) P->next=P->next->next;
    (4) P=P->next->next;
    (5) while(P!=NULL) P=P->next;
    (6) while(Q->next!=NULL) { P=Q; Q=Q->next; }
    (7) while(P->next!=Q) P=P->next;
    (8) while(P->next->next!=Q) P=P->next;
    (9) while(P->next->next!=NULL) P=P->next;
    (10) Q=P;
    (11) Q=P->next;
    (12) P=L;
    (13) L=L->next;
    (14) free(Q);

    解:a. (11) (3) (14)
    b. (10) (12) (8) (3) (14)
    c. (10) (12) (7) (3) (14)
    d. (12) (11) (3) (14)
    e. (9) (11) (3) (14)

    2.8 已知P结点是某双向链表的中间结点,试从下列提供的答案中选择合适的语句序列。

    a. 在P结点后插入S结点的语句序列是_______________________。
    b. 在P结点前插入S结点的语句序列是_______________________。
    c. 删除P结点的直接后继结点的语句序列是_______________________。
    d. 删除P结点的直接前驱结点的语句序列是_______________________。
    e. 删除P结点的语句序列是_______________________。
    (1) P->next=P->next->next;
    (2) P->priou=P->priou->priou;
    (3) P->next=S;
    (4) P->priou=S;
    (5) S->next=P;
    (6) S->priou=P;
    (7) S->next=P->next;
    (8) S->priou=P->priou;
    (9) P->priou->next=P->next;
    (10) P->priou->next=P;
    (11) P->next->priou=P;
    (12) P->next->priou=S;
    (13) P->priou->next=S;
    (14) P->next->priou=P->priou;
    (15) Q=P->next;
    (16) Q=P->priou;
    (17) free§;
    (18) free(Q);
    解:a. (7) (6) (12)(3) (12和3的位置不能反,反了就错了)
    b. (8) (5) (13)(4)
    c. (15) (1) (11) (18)
    d. (16) (2) (10) (18)
    e. (14) (9) (17)

    2.11 设顺序表va中的数据元素递增有序。试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。

    解:

    Status InsertOrderList(SqList &va,ElemType x)
    {
    	//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法
    	int i;
    	if(va.length==va.listsize)return(OVERFLOW);
    	for(i=va.length;i>0,x<va.elem[i-1];i--)
    		va.elem[i]=va.elem[i-1];
    	va.elem[i]=x;
    	va.length++;
    	return OK;
    }
    

    其他写法:
    答:因已知顺序表L是递增有序表,所以只要从顺序表终端结点(设为i位置元素)开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。
      在寻找过程中,由于大于x的元素都应放在x之后,所以可边寻找,边后移元素,当找到第一个小于或等于x的元素位置i时,该位置也空出来了。
      算法如下:

    //顺序表存储结构如题2.7
        void InsertIncreaseList( Seqlist *L , Datatype x )
         { 
          int i;
          if ( L->length>=ListSize)
           Error(“overflow");
          for ( i=L -> length ; i>0 && L->data[ i-1 ] > x ; i--)
           L->data[ i ]=L->data[ i-1 ] ; // 比较并移动元素
          L->data[ i ] =x;
          L -> length++;
         }
    

    2.21 试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表 逆置为 。

    解:

    // 顺序表的逆置
    Status ListOppose_Sq(SqList &L)
    {
    	int i;
    	ElemType x;
    	for(i=0;i<L.length/2;i++){
    		x=L.elem[i];
    		L.elem[i]=L.elem[L.length-1-i];
    		L.elem[L.length-1-i]=x;
    	}
    	return OK;
    }
    

    其他写法:
    答:
      要将该表逆置,可以将表中的开始结点与终端结点互换,第二个结点与倒数第二个结点互换,如此反复,就可将整个表逆置了。算法如下:

    // 顺序表结构定义同上题
    
     void ReverseList( Seqlist *L)
      {
       DataType temp ; //设置临时空间用于存放data
       int i;
       for (i=0;i<L->length/2;i++)//L->length/2为整除运算
        { temp = L->data[i]; //交换数据
         L -> data[ i ] = L -> data[ L -> length-1-i];
         L -> data[ L -> length - 1 - i ] = temp;
        }
      }
    

    2.24 假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构,请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序,允许表中含有值相同的元素)排列的线性表C,并要求利用原表(即A表和B表)的结点空间构造C表。

    解:

    // 将合并逆置后的结果放在C表中,并删除B表
    Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)
    {
    	LinkList pa,pb,qa,qb;
    	pa=A;
    	pb=B;
    	qa=pa;	// 保存pa的前驱指针
    	qb=pb;	// 保存pb的前驱指针
    	pa=pa->next;
    	pb=pb->next;
    	A->next=NULL;
    	C=A;
    	while(pa&&pb){
    		if(pa->data<pb->data){
    			qa=pa;
    			pa=pa->next;
    			qa->next=A->next;	//将当前最小结点插入A表表头
    			A->next=qa;
    		}
    		else{
    			qb=pb;
    			pb=pb->next;
    			qb->next=A->next;	//将当前最小结点插入A表表头
    			A->next=qb;
    		}
    	}
    	while(pa){
    		qa=pa;
    		pa=pa->next;
    		qa->next=A->next;
    		A->next=qa;
    	}
    	while(pb){
    		qb=pb;
    		pb=pb->next;
    		qb->next=A->next;
    		A->next=qb;
    	}
    	pb=B;
    	free(pb);
    	return OK;
    }
    

    其他写法:
    解:

    void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间
    {
      pa=A->next;pb=B->next;pre=NULL; //pa和pb分别指向A,B的当前元素
      while(pa||pb)
      {
        if(pa->data<pb->data||!pb)
        {
          pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表
        }
        else
        {
          pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表
        }
        pre=pc;
      }
      C=A;A->next=pc; //构造新表头
    }//reverse_merge
    

    分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.

    2.31 假设某个单向循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。

    解:

    // 在单循环链表S中删除S的前驱结点
    Status ListDelete_CL(LinkList &S)
    {
    	LinkList p,q;
    	if(S==S->next)return ERROR;
    	q=S;
    	p=S->next;
    	while(p->next!=S){
    		q=p;
    		p=p->next;
    	}
    	q->next=p->next;
    	free(p);
    	return OK;
    }
    

    其他写法:
    解:
      已知指向这个结点的指针是s,那么要删除这个结点的直接前趋结点,就只要找到一个结点,它的指针域是指向s的直接前趋,然后用后删结点法,将结点*s的直接前趋结点删除即可。

    算法如下:

     void DeleteNode( ListNode *s)
        {//删除单循环链表中指定结点的直接前趋结点
          ListNode *p, *q;
          p=s;
          while( p->next->next!=s) 
           p=p->next;
          //删除结点
          q=p->next;
          p->next=q->next;
          free(p); //释放空间
        }
    

    注意:
      若单循环链表的长度等于1,则只要把表删空即可。

    2.32 已知有一个单向循环链表,其每个结点中含三个域:pre,data和next,其中data为数据域,next为指向后继结点的指针域,prior也为指针域,但它的值为空(NULL),试编写算法将此单向循环链表改为双向循环链表,即使prior成为指向前驱结点的指针域。

    解:

    // 建立一个空的循环链表
    Status InitList_DL(DuLinkList &L)
    {
    	L=(DuLinkList)malloc(sizeof(DuLNode));
    	if(!L) exit(OVERFLOW);
    	L->pre=NULL;
    	L->next=L;
    	return OK;
    }
    	// 向循环链表中插入一个结点
    Status ListInsert_DL(DuLinkList &L,ElemType e)
    {
    	DuLinkList p;
    	p=(DuLinkList)malloc(sizeof(DuLNode));
    	if(!p) return ERROR;
    	p->data=e;
    	p->next=L->next;
    	L->next=p;
    	return OK;
    }
    	// 将单循环链表改成双向链表
    Status ListCirToDu(DuLinkList &L)
    {
    	DuLinkList p,q;
    	q=L;
    	p=L->next;
    	while(p!=L){
    		p->pre=q;
    		q=p;
    		p=p->next;
    	}
    	if(p==L) p->pre=q;
    	return OK;
    }
    其他写法:
    Status DuLNode_Pre(DuLinkList &L)//完成双向循环链表结点的pre域
    {
      for(p=L;!p->next->pre;p=p->next) p->next->pre=p;
      return OK;
    }//DuLNode_Pre 
    

    第3章 栈和队列

    3.2 简述栈和线性表的差别。

    解:线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。

    3.3 写出下列程序段的输出结果(栈的元素类型SElemType为char)。

    void main()
    	{
    		Stack S;
    		char x,y;
    		InitStack(S);
    		x= ‘c’; y= ‘k’;
    		Push(S,x);	Push(S, ‘a’);	Push(S,y);
    		Pop(S,x);	Push(S, ‘t’);	Push(S,x);
    		Pop(S,x);	Push(S, ‘s’);
    		while(!StackEmpty(S)) { Pop(S,y); printf(y); }
    		printf(x);
    	}
    

    解:stack
    void main( ){
    Stack S;
    Char x,y;
    InitStack(S);
    x=’c’;y=’k’; //x=‘c’, y=‘k’
    Push(S,x); //x=‘c’,y=‘k’,S=“c”
    Push(S,’a’); //x=‘c’,y=‘k’,S=“ac”
    Push(S,y); //x=‘c’, y=‘k’, S=“kac”
    Pop(S,x); //x=‘k’,y=‘k’,S=“ac”
    Push(S,’t’); //x=‘k’,y=‘k’,S=“tac”
    Push(S,x); //x=‘k’,y=‘k’,S=“ktac”
    Pop(S,x); //x=‘k’,y=‘k’ S=“tac”
    Push(S,’s’); //x=‘k’,y=‘k’ S=“stac”
    while(!StackEmpty(S))
    {
    Pop(S,y); //依次为y=‘s’,y=‘t’,y=‘a’,y=‘c’
    printf(y); //打印依次为s,t,a,c
    }
    Printf(x);//x=‘k’
    }
    所以最后应该是stack

    3.12 写出以下程序段的输出结果(队列中的元素类型QElemType为char)。

    void main()
    	{
    		Queue Q;
    		InitQueue(Q);
    		char x= ‘e’, y= ‘c’;
    		EnQueue(Q, ‘h’);
    		EnQueue(Q, ‘r’);
    		EnQueue(Q, y);
    		DeQueue(Q, x);
    		EnQueue(Q, x);
    		DeQueue(Q, x);
    		EnQueue(Q, ‘a’);
    		While(!QueueEmpty(Q))
    		{
    			DeQueue(Q,y);
    			cout<<y;
    		}
    		cout<<x;
    	}
    

    解:char

    3.28 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化、入队列和出队列的算法。

    解:

    typedef int ElemType;
    typedef struct NodeType{
    	ElemType data;
    	NodeType *next;
    }QNode,*QPtr;
    typedef struct{
    	QPtr rear;
    	int size;
    }Queue;
    Status InitQueue(Queue& q)
    {
    	q.rear=NULL;
    	q.size=0;
    	return OK;
    }
    Status EnQueue(Queue& q,ElemType e)
    {
    	QPtr p;
    	p=new QNode;
    	if(!p) return FALSE;
    	p->data=e;
    	if(!q.rear){
    		q.rear=p;
    		p->next=q.rear;
    	}
    	else{
    		p->next=q.rear->next;
    		q.rear->next=p;
    		q.rear=p;
    	}
    	q.size++;
    	return OK;
    }
    Status DeQueue(Queue& q,ElemType& e)
    {
    	QPtr p;
    	if(q.size==0)return FALSE;
    	if(q.size==1){
    		p=q.rear;
    		e=p->data;
    		q.rear=NULL;
    		delete p;
    	}
    	else{
    		p=q.rear->next;
    		e=p->data;
    		q.rear->next=p->next;
    		delete p;
    	}
    	q.size--;
    	return OK;
    }
    

    其他解法:

    3.13 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针) ,试编写相应的置空队、判队空 、入队和出队等算法。

    解:算法如下:

    //先定义链队结构:
     typedef struct queuenode{
       Datatype data;
       struct queuenode *next;
      }QueueNode; //以上是结点类型的定义
     typedef struct{
       queuenode *rear;
      }LinkQueue; //只设一个指向队尾元素的指针
    

    (1)置空队

    void InitQueue( LinkQueue *Q)
       { //置空队:就是使头结点成为队尾元素
        QueueNode *s;
        Q->rear = Q->rear->next;//将队尾指针指向头结点
        while (Q->rear!=Q->rear->next)//当队列非空,将队中元素逐个出队
         {s=Q->rear->next;
          Q->rear->next=s->next;
          free(s);
         }//回收结点空间
       }
    

    (2)判队空

    int EmptyQueue( LinkQueue *Q)
       { //判队空
        //当头结点的next指针指向自己时为空队
        return Q->rear->next->next==Q->rear->next;
       }

    (3)入队

    void EnQueue( LinkQueue *Q, Datatype x)
       { //入队
        //也就是在尾结点处插入元素
        QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点
        p->data=x; p->next=Q->rear->next;//初始化新结点并链入
        Q-rear->next=p; 
        Q->rear=p;//将尾指针移至新结点
       }
    

    (4)出队

    Datatype DeQueue( LinkQueue *Q)
       {//出队,把头结点之后的元素摘下
        Datatype t;
        QueueNode *p;
        if(EmptyQueue( Q ))
          Error("Queue underflow");
        p=Q->rear->next->next; //p指向将要摘下的结点
        x=p->data; //保存结点中数据
        if (p==Q->rear)
         {//当队列中只有一个结点时,p结点出队后,要将队尾指针指向头结点
          Q->rear = Q->rear->next; Q->rear->next=p->next;}
        else 
          Q->rear->next->next=p->next;//摘下结点p
        free(p);//释放被删结点
        return x;
       }
    

    3.30 假设将循环队列定义为:以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件,并写出相应的入队列和出队列的算法(在出队列的算法中要返回队头元素)。

    解:

    #define MaxQSize	4
    typedef int ElemType;
    typedef struct{
    	ElemType *base;
    	int rear;
    	int length;
    }Queue;
    Status InitQueue(Queue& q)
    {
    	q.base=new ElemType[MaxQSize];
    	if(!q.base) return FALSE;
    	q.rear=0;
    	q.length=0;
    	return OK;
    }
    Status EnQueue(Queue& q,ElemType e)
    {
    	if((q.rear+1)%MaxQSize==(q.rear+MaxQSize-q.length)%MaxQSize)
    		return FALSE;
    	else{
    		q.base[q.rear]=e;
    		q.rear=(q.rear+1)%MaxQSize;
    		q.length++;
    	}
    	return OK;
    }
    Status DeQueue(Queue& q,ElemType& e)
    {
    	if((q.rear+MaxQSize-q.length)%MaxQSize==q.rear)
    		return FALSE;
    	else{
    		e=q.base[(q.rear+MaxQSize-q.length)%MaxQSize];
    		q.length--;
    	}
    	return OK;
    }
    

    其他写法:

    3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数,试给出判别此循环队列的队满条件,并写出相应的入队和出队算法,要求出队时需返回队头元素。

    解:根据题意,可定义该循环队列的存储结构:

     #define QueueSize 100 
     typedef char Datatype ; //设元素的类型为char型
     typedef struct {
       int quelen;
       int rear;
       Datatype Data[QueueSize];
      }CirQueue; 
     CirQueue *Q;
    

    循环队列的队满条件是:Q->quelen== QueueSize
      知道了尾指针和元素个数,当然就能计算出队头元素的位置。算法如下:
     (1)判断队满

    int FullQueue( CirQueue *Q)
        {//判队满,队中元素个数等于空间大小
          return Q->quelen== QueueSize;
        }
    

    (2)入队

    void EnQueue( CirQueue *Q, Datatype x)
        {// 入队
         if(FullQueue( Q))
          Error("队已满,无法入队");
         Q->Data[Q->rear]=x;
         Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1
         Q->quelen++;
        }
    

    (3)出队

    Datatype DeQueue( CirQueue *Q)
        {//出队
         if(Q->quelen==0)
          Error("队已空,无元素可出队");
         int tmpfront; //设一个临时队头指针
         tmpfront=(QueueSize+Q->rear - Q->quelen+1)%QueueSize;//计算头指针位置
         Q->quelen--;
         return Q->Data[tmpfront];
        }
    

    第六章树和二叉树

    6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

    解:含三个结点的树只有两种:(1)和(2);而含3个结点的二叉树可能有下列3种形态:(一),(二),(三),(四),(五)。

    在这里插入图片描述

    注意,(2)和(三)是完全不同的结构。

    6.15 请对右图所示二叉树进行后序线索化,为每个空指计建立相应的前驱或后继线索

    解:
    在这里插入图片描述

    6.27假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。

    解:

    在这里插入图片描述

    6.28假设一棵二叉树的中序序为DCBGEAHFIJK和后序序列为DCEGBFHKJIA.请画出该树。

    解:

    在这里插入图片描述

    展开全文
  • 数据结构与算法复习 选择 TOC \o "1-5" \h \z ?在数据结构中从逻辑上可以把数据结构分为 C A.动态结构和静态结构 B ?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 ?数据结构在计算机内存...
  • 很好的数据结构与算法期末考试试卷!对大家的考试应该很有帮助!
  • 北京科技大学2014年数据结构与算法期末考试试卷及答案,包含选择,填空,计算等,文档为电子版,下载后可直接打印。
  • C语言期末考试题库+十套数据结构与算法试题及答案+实验报告 1. 十套数据结构试题及答案.doc 2. C语言期末题库.docx 3. 数据结构与算法实验报告:对应线性表;栈和队列;树和二叉树;图。
  • 四川大学期末考试试题 2013-2014学年第1学期 课程号 课程名称 数据结构与算法分析A卷 任课教师 适用专业年级 学号 姓名 考试须知 四川大学学生参加由学校组织或由学校承办的各级各类考试必须严格执行四川大学考试...
  • 福州大学2006级《算法与数据结构期末上机考试试题.pdf
  • 四川大学计算机学院数据结构与算法分析期末真题2018-2019学年第1学期A、B卷(含答案评分标准) #资源达人分享计划#
  • 课程名称数据结构与算法分析 任课教师 学号 姓名 本 NUMPAGES 2页本页为第 PAGE 2页 教务处试题编号 注试题字迹务必清晰书写工整 本 NUMPAGES 2页本页为第 PAGE 1页 教务处试题编号 四川大学期末考试试题 2013-...
  • 哈尔滨工业大学数据结构与算法2012年的期末考试试题以及答案,供备考的同学们使用。
  • 2015年数据结构与算法A期末考试试题 姓名_ 学号_ 任课教师 考场_ 题号 一 二 三 四 总分 得分 注意事项 全部题目都在空白答题纸上解答 本试卷对算法设计都有质量要求请尽量按照试题中的要求来写算法否则将酌情扣分 ...
  • 数据结构与算法期末练习 一 选择 1.以下数据的存储结构无关的术语是( D )。 A.循环队列 B. 链表 C. 哈希表 D. 栈 2. 算法的时间复杂度取决于( A ) A.问题的规模 B. 待处理数据的初态 C. A和B D. ...
  • 浙江中医药大学-数据结构与算法期末考试(A、B)(2017.1.11)应用、程序设计 一、应用 1、设一颗二叉树的先序序列:A B D F C E G H,中序序列:B F D A G E H C。  Q1:画出这颗二叉树。  Q2:画出这颗...
    浙江中医药大学-数据结构与算法期末考试(A、B)(2017.1.11)应用题、程序设计题

    一、应用题
    1、设一颗二叉树的先序序列:A B D F C E G H,中序序列:B F D A G E H C。
          Q1:画出这颗二叉树。
          Q2:画出这颗二叉树的后序线索树。
          Q3:将这颗二叉树转化成对应的树(或森林)。

    R1:根据先序序列的遍历特点(先访问根结点->左子树->右子树),确定A是这颗二叉树的根结点,根据中序序列的特点(先访问左子树->根结点->右子树),确定根结点左部必定全是左子树的子孙(B F D),其右部必定全部是右子树的子孙(G E H C)。


    R2:先写出这颗二叉树的后序遍历:F D B G H E C A。


    R3:拎葡萄


    2、

    已知如图所示的无向网,请给出:

       ① 邻接矩阵;    

       ② 邻接表;

       ③ 最小生成树



    R1:在矩阵外最好写上字母,不会看花



    R2:



    R3:

    使用克鲁斯卡尔算法:将权值从小到大进行排列,直至所有顶点在同一连通分量上。



    4、(A卷)假定对有序表:(34572430425463728795)进行折半查找,试回答下列问题:

       ① 画出描述折半查找过程的判定树;

      ② 若查找元素54,需依次与哪些元素比较?

      ③ 若查找元素90,需依次与哪些元素比较?

          ④ 假定每个元素的查找概率相等,求查找成功时的平均查找长度。



    5、(B卷)在一棵空的二叉排序树中依次插入关键字序列为12,7,17,11,16,2,13,9,21,4,试回答下列问题:

                    画出这棵二叉排序树;

       若查找元素21,需依次与哪些元素比较?

       ③若查找元素10,需依次与哪些元素比较?

             ④ 假定每个元素的查找概率相等,求查找成功时的平均查找长度。

    思路:与4相似,这里是二叉排序树,以12作为根结点,左子树<根结点,右子树>根结点。



    6、设计算法,统计二叉树的叶结点个数。

    int LeafNodeCount(BiTree T)
    {
    	if(T==NULL)
    		return 0; //如果是空树,则叶子结点个数为0
    	else if(T->lchild==NULL&&T->rchild==NULL)
    		return 1; //判断结点是否是叶子结点(左孩子右孩子都为空),若是则返回1
    	else
    		return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);
    }
    
         7、 统计出不带表头的单链表HL中结点的值等于给定值X的结点数写出实现算法。

             typedef struct node {

    int data;

            struct node *next;

    }lklist

    int CountX(lklist * HL,ElemType x)
    {  
    int i=0;
    LNode* p=HL;//i为计数器
    while(p!=NULL) {
    if (P->data==x) i++;
    p=p->next;
    }//while, 出循环时i中的值即为x结点个数
    return i;
    }//CountX
    
          8、 设计一个算法,删除递增有序链表中值大于mink且小于maxk的所有元素(mink和maxk是给定的两个参数,其值可以和表中的元素相同,也可以不同 )。

    void delete(LinkList &L, int mink, int maxk) {
       p=L->next; //首元结点
       while (p && p->data<=mink)
          { pre=p;  p=p->next; } //查找第一个值>mink的结点
       if (p) 
    {while (p && p->data<maxk)  
          p=p->next;
                          // 查找第一个值 ≥maxk的结点
          q=pre->next;   pre->next=p;  // 修改指针
          while (q!=p) 
             { s=q->next;  delete q;  q=s; } // 释放结点空间
       }//if
    }
    
      9、见blog第二章:顺序表、单链表的删除(程序设计)




    展开全文
  • 四川大学期末考试试题 2007-2008学年第1学期 课程号 课程名称 数据结构与算法分析B卷 任课教师 适用专业年级 06级软件工程 学号 姓名 考试须知 四川大学学生参加由学校组织或由学校承办的各级各类考试必须严格执行...
  • 9.90 积分数据结构与算法期末实验考试成绩表学号姓名专业班123成绩签名0051448张良计算机科学技术0510053720刘太军软件工程0520077271肖雪梅信息管理信息系统0720082586郑海峰计算机科学技术0810082.....

    a7f4a3f590493a1e451dd952a488fd7c.gif 数据结构 数据结构与算法期末实验考试成绩表.doc

    (2页)

    61773f911215430a431692fc5f605802.gif

    本资源提供全文预览,点击全文预览即可全文预览,如果喜欢文档就下载吧,查找使用更方便哦!

    9.90 积分

    数据结构与算法期末实验考试成绩表学号姓名专业班题1题2题3成绩签名0051448张良计算机科学与技术0510053720刘太军软件工程0520077271肖雪梅信息管理与信息系统0720082586郑海峰计算机科学与技术0810082619杨宏俊计算机科学与技术0810093988李文聪计算机科学与技术0910093991尹玲琳计算机科学与技术0910093993张昆计算机科学与技术0910093995刘琳计算机科学与技术0910093997王涛涛计算机科学与技术0910093999赖昆锌计算机科学与技术0910094002蓝震宇计算机科学与技术0910094004付鹏计算机科学与技术0910094005胡贤利计算机科学与技术0910094006刘松计算机科学与技术0910094007李洋锋计算机科学与技术0910094010肖筱馨茹计算机科学与技术0910094014姜吉西计算机科学与技术0910094017刘芳计算机科学与技术0910094019黎凯计算机科学与技术0910094021李波龙计算机科学与技术0910094022梁雨农计算机科学与技术0910094034刘鑫计算机科学与技术0920094036宋永珍计算机科学与技术0920094040邱慧莲计算机科学与技术0920094041章逸群计算机科学与技术0920094044闵娜计算机科学与技术0920094045付昊计算机科学与技术0920094047成云峰计算机科学与技术0920094048刘剑锋计算机科学与技术0920094051黄樑计算机科学与技术0920094052黄旋计算机科学与技术0920094053金幼华计算机科学与技术0920094054刘琳计算机科学与技术0920094056李路计算机科学与技术0920094058吴桂禄计算机科学与技术0920094064章园计算机科学与技术0920094071董皓计算机科学与技术0920094074刘松波计算机科学与技术0920094079梁泳天计算机科学与技术092 关 键 词: 结构 数据 期末 算法 实验 考试 成绩

    4d91c43bfc72ca913299809b07b4968f.gif  天天文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。

    关于本文

    展开全文
  • 哈工大数据结构13年期末试卷
  • 北京大学信息科学技术学院考试试卷 考试科目数据结构与算法A 姓名 学号 考试时间 2018 年 1 月 3 日 任课教师: 一 二 三 四 五 六 题号 总分 10 15 5 10 30 30 分数 装 订 阅卷人 线 内 北京大学考场纪律 1考生进入...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,842
精华内容 3,136
关键字:

数据结构与算法期末题

数据结构 订阅