海康威视嵌入式BSP笔试

笔试"/>

海康威视嵌入式BSP笔试

1、若进栈序列为1,2,3,4，进栈的过程中可以出栈，则下列不可能的一个出栈序列是（）

• A、3,4,2,1 
• B   3,1,4,2
• C   1,4,3,2
• D   2,3,4,1

答案：B
析：栈空间是先进后出，后进先出。B选项，3若要先出，则栈中肯定有，3,2,1三个，因此下一个出栈的只能是2或者4。

2、采用链表的方式完成队列的插队和出队，参阅下述结构体：

typedef struct _QUEUE_NODE_
{struct _QUEUE_NODE_ *pNextNode;  //下一个结点指针void *pData;                     //结点数据
}QUEUE_NODE,*PQUEUE_NODE;typedef struct
{QUEUE_NODE *pHeadNode; //头指针QUEUE_NODE *pTailNode; //尾指针
}QUEUE_HANDLE,*PQUEUE_HANDLE;

 注：
   队列 (Queue) ，是一种先进先出 (First In First Out ,简称 FIFO) 的线性表。只允许在表的一端进行插入,而在另一端进行删除。 
   队首 (front) :允许进行删除的一端称为队首。 
   队尾 (rear) :允许进行插入的一端称为队尾。

知识点：数据结构 —— 队列、栈、链表的区别​​​​​​​

//插队
void Insert_Queue(QUEUE_HANDLE *q,void *data)
{if(q==NULL){printf("Error:q is NULL!\n");exit(1);}QUEUE_NODE *new_node = (QUEUE_NODE *)malloc(sizeof(QUEUE_NODE));if(new_node == NULL){printf("malloc error!\n");exit(1);}new_node->pData = data;new_node->pNextNode = NULL;if(q->pTailNode==NULL&&q->pTailNode==NULL){q->pTailNode = new_node;q->pHeadNode = new_node;}else{q->pTailNode->pNextNode = new_node;q->pTailNode = new_node;}}

//出队 
void Del_Queue(QUEUE_HANDLE *q)
{if(q ==NULL){printf("Error:q is NULL!\n");exit(1);} QUEUE_NODE *del_node = q->pHeadNode;if(q->pHeadNode ==NULL)return;if(q->pHeadNode!=NULL){if(q->pHeadNode->pNextNode == NULL){q->pHeadNode =  NULL; q->pTailNode =  NULL;free(del_node);} else{q->pHeadNode = q->pHeadNode->pNextNode;free(del_node);}}} 

链表实现出队入队的完整代码实现：

#include<stdio.h>
#include<stdlib.h>
typedef struct _QUEUE_NODE_
{struct _QUEUE_NODE_ *pNextNode; //下一个结点指针void *pData;					//结点数据 
}QUEUE_NODE,*PQUEUE_NODE;typedef struct
{QUEUE_NODE *pHeadNode; //队列头指针QUEUE_NODE *pTailNode;//队列尾指针 } QUEUE_HANDLE,*PQUEUE_HANDLE;//插队
void Insert_Queue(QUEUE_HANDLE *q,void *data)
{if(q==NULL){printf("Error:q is NULL!\n");exit(1);}QUEUE_NODE *new_node = (QUEUE_NODE *)malloc(sizeof(QUEUE_NODE));if(new_node == NULL){printf("malloc error!\n");exit(1);}new_node->pData = data;new_node->pNextNode = NULL;if(q->pTailNode==NULL&&q->pTailNode==NULL){q->pTailNode = new_node;q->pHeadNode = new_node;}else{q->pTailNode->pNextNode = new_node;q->pTailNode = new_node;}}
//出队 
void Del_Queue(QUEUE_HANDLE *q)
{if(q ==NULL){printf("Error:q is NULL!\n");exit(1);} QUEUE_NODE *del_node = q->pHeadNode;if(q->pHeadNode ==NULL)return;if(q->pHeadNode!=NULL){if(q->pHeadNode->pNextNode == NULL){q->pHeadNode =  NULL; q->pTailNode =  NULL;free(del_node);} else{q->pHeadNode = q->pHeadNode->pNextNode;free(del_node);}}} //遍历队列void Queue_List(QUEUE_HANDLE *q){int i =0;QUEUE_NODE *pp = q->pHeadNode;printf("当前队列："); while(pp){i++;printf("%c",pp->pData);pp = pp->pNextNode;}	printf("\n");}int main(){int length = 10;int j = length;QUEUE_HANDLE *q = (QUEUE_HANDLE *)malloc(sizeof(QUEUE_HANDLE));q->pHeadNode = q->pTailNode = NULL;void *data = NULL;printf("入队：\n"); while(length){data = (void *)('a'+j-length);Insert_Queue(q,data);Queue_List(q);length--;}Queue_List(q);printf("出队：\n"); while(j){Del_Queue(q);Queue_List(q);j--;}if(q->pHeadNode==q->pTailNode)printf("Queue is empty!\n");return 0;}

运行结果：

入队：
当前队列：a
当前队列：ab
当前队列：abc
当前队列：abcd
当前队列：abcde
当前队列：abcdef
当前队列：abcdefg
当前队列：abcdefgh
当前队列：abcdefghi
当前队列：abcdefghij
当前队列：abcdefghij
出队：
当前队列：bcdefghij
当前队列：cdefghij
当前队列：defghij
当前队列：efghij
当前队列：fghij
当前队列：ghij
当前队列：hij
当前队列：ij
当前队列：j
当前队列：
Queue is empty!--------------------------------
Process exited after 2.554 seconds with return value 0
请按任意键继续. . .